Научность тезиса Черча-Тьюринга

Определение тезиса Черча-Тьюринга - это попытка уловить интуитивную идею эффективной вычислимости или «вещей, которые действительно можно вычислить».

Было сказано, что это не то, что нужно доказывать или опровергать, но важные предположения, лежащие в основе научной работы во многих областях исследований, основаны на той или иной версии тезиса, одним из важных случаев является лингвистическое предположение о том, что семантика естественных языков может быть формализуется каким- либо существенным образом .

Учитывая его нефальсифицируемость, следует ли отводить тезису Черча-Тьюринга такую ​​важную роль в научных исследованиях?

РЕДАКТИРОВАТЬ:

Спасибо за внимание. В ответ на некоторую критику, которую получил вопрос, я хотел бы добавить, что

  1. Во многих-многих работах по лингвистике, психологии, когнитивистике, философии и, очевидно, в большей части того, что относится к прикладной информатике, делается более или менее сознательный скачок от мысли-смысл-поведения... к вычислимому к вычислимому по Тьюрингу . Именно на этот последний шаг я ссылаюсь в этом вопросе. Такой образ мышления, хотя и не обязательно отражающий наше лучшее понимание, по-прежнему пользуется значительной популярностью в научном сообществе (и да, это только мое восприятие).
  2. Тезис Черча-Тьюринга, не будучи полностью объективным, все еще может быть предметом споров, возражений, даже дискредитации и, в конечном счете, сочтен бесполезным (что, я верю, когда-нибудь и произойдет), но строго фальсифицировать его нельзя .
Никто не верит, что семантику естественных языков можно формализовать. Даже Дэвидсон, который, как мне кажется, был наиболее оптимистичен в этом отношении, рассматривает его как регулятивный идеал, к которому мы должны стремиться, а не как предположение. Что-то вроде давайте попробуем формализовать как можно больше. «Закон» причинности также не поддается фальсификации (и, возможно, ложен), однако продолжать искать причины там, где их еще не нашли, по-прежнему в основном является хорошим девизом для науки. Закономерность или эффективная вычислимость — хорошие цели, потому что они очень полезны для нас, пока они не превращаются в принятие желаемого за действительное.
«Никто не верит» — сильное заявление, особенно в этом сообществе. Я считаю, что об этом стоит поговорить.
Но вы называете это «важным допущением, лежащим в основе научной работы во многих областях», а это не так. «Никто» — это не большая натяжка, см. «Философию языка» Миллера. Это просто не нужно в качестве допущения для лингвистики естественных языков или даже для попытки формализации ее аспектов.
иначе говоря, люди, которые предполагают , что семантика естественных языков может быть формализована, рискуют быть не принятыми всерьез.
Я не уверен, что вы правильно охарактеризовали КТ. Именно Тьюринг, и только Тьюринг, уловил понятие «эффективная процедура» в формальных терминах. КТ, если не ошибаюсь, говорит, что другие модели, вроде лямбда-исчисления, эквивалентны модели Тьюринга. это совсем другое. это никогда не было доказано, но это не значит, что это не может быть доказано. тем не менее все верят, что это правда.
«многие области исследований опираются на ту или иную версию тезиса». можно конкретный пример? Я не могу думать ни об одном.
@mobileink, если вы внимательно прочитаете вопрос, вы очень легко найдете пример. Вы (и другие) можете не соглашаться с тем, что это правильный пример, но он есть.
Мы можем сказать, что тезис Черча-Тьюринга — это гипотеза; мы не можем математически доказать это, потому что оно устанавливает эквивалентность между «формальным» понятием и интуитивным. Конечно, его можно сфальсифицировать (и попытки были предприняты). Как ? демонстрируя «вычислительную процедуру», которая является интуитивно «механической», но доказывает (точным математическим способом), что она, например, не вычислима по Тьюрингу.
См. также этот пост .

Ответы (2)

Вы должны быть осторожны, когда используете слово «наука» в контексте фальсифицируемости. Опровержимость — это свойство теорий эмпирических наук, т. е. наук, основанных на наблюдении за явлениями реального мира.

В этом смысле тезис Черча-Тьюринга не является научным утверждением, это утверждение логики и математики. Логика и математика не зависят от наблюдения и поэтому, строго говоря, не являются частью науки. 2+2=4 независимо от того, верна ли ньютоновская механика или верна теория относительности Эйнштейна. (ab)²= a² - 2ab + b² независимо от того, плоская ли Земля, или круглая, или в Солнечной системе 25 планет или только 4.

В некоторых других определениях математика и логика являются науками, но, используя критерии разграничения Фальсификации, они ими не являются.

Что касается того факта, что тезис Черча-Тьюринга используется в различных эмпирических науках, то он имеет к этим наукам такое же отношение, как любая теорема или математическая гипотеза к ним.

Вы рискуете намекнуть, что информатика — это не наука.
Теоретическая информатика — это не эмпирическая наука, это определенно раздел математики. Это началось как раздел математики, когда Тьюринг решил решить одну из проблем Гильберта. Но теперь вы заставили меня наткнуться на более интересный вопрос......
Я не думаю, что это правильно. Теорема математики может быть доказана из первых принципов. Тезис КТ не является теоремой и не может быть логически доказан. Это заявление о вере в мир. В мире не может быть двух вещей, более разных и непохожих, чем математическая теорема и тезис Черча-Тьюринга.
@ user4894 Я никогда не говорил, что это теорема. Тезис Черча-Тьюринга относится к тому же типу утверждений, что и утверждения математики в смысле юмовской вилки , т. е. они представляют собой отношения идей, а не фактов о мире. Вы путаете исходный тезис Черча-Тьюринга с обновленной физической версией тезиса Дэвида Дойча , которая представляет собой утверждение фактов о мире.
Вы считаете математику эмпирической наукой?
извините, это должно было быть адресовано @user4894
Я согласен, что CSIS не является эмпирической наукой. Но «определенно раздел математики» — это совсем другая история. Концепция вычислений основана на интуитивном понятии «эффективной процедуры», и я не вижу причин рассматривать это как математическое понятие.
@mobileink Я думаю, я понял ваш посыл: эффективная процедура - это скорее человеческий артефакт, чем независимая истина, поэтому вы не согласны? Но то же самое относится и к преобразованию Фурье или факторизации матрицы LU, но это все еще математические объекты, о которых можно сформулировать теоремы, а не физические объекты, см. здесь
есть часть, где вы говорите это, и часть, где вы берёте это обратно, как однажды сказал кто-то известный. геометрия также основана на интуиции, полученной из опыта жизни в пространстве, так же как вычисление основано на интуиции, полученной из живого опыта вычислений. так почему бы последнему не быть таким же математическим, как и первому? один из возможных ответов: теория вычислений — это математическая модель чего-то нематематического. но я думаю, то же самое можно сказать и о Евклиде, геометрии и пространстве.
Я склонен думать о математике, логике и вычислениях как о разных взглядах на одну вещь. есть проблемы с коронацией любого из них и рассмотрением других как производных. Может быть, они в конечном счете независимы?
@AlexanderSKing Классический тезис CT гласит, что TM может вычислить все, что может быть эффективно вычислено человеком . Это явное утверждение о мире . Утверждения математики НЕ являются утверждениями о мире. Вот почему я с вами не согласен. en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
@mobileink Математика часто черпается из реального мира. Но математическая теорема не о мире. КТ явно о мире в том смысле, что он относится к способностям людей. Математические теоремы являются лишь формальными следствиями аксиом и правил вывода. Они не обязательно связаны с миром. Тезис КТ явно касается мира. Это огромное отличие, которого не хватает Александру С. Кингу.
@ user4894 Википедия может не быть окончательным источником, но даже в ней используется фраза «человек следует алгоритму» для того, к чему она применима в реальном мире. Для меня это дополнительное ограничение является ключом к интерпретации CT как формального результата, хотя он может одновременно отражать вещи «в реальном мире» (т. е. воплощать конкретную формализацию алгоритма) и может представлять реальное ограничение на что может произойти «в реальном мире» (может быть, это показатель того, что возможно аля Дойч).
@ user4894 UTM — это математические объекты, λ-исчисление — это формальная система, т. е. набор математических объектов, общерекурсивные функции Гёделя — это математические объекты. Классическая КТ — это гипотеза о том, что свойство этих трех классов математических объектов применимо и к большему набору математических объектов. Классическая КТ проблематична, потому что этот более общий класс не имеет четкого определения, а не из-за эмпирического характера тезиса. Я согласен с вами, что его можно интерпретировать как имеющее эмпирические последствия, но тогда он становится тезисом Дойч-КТ, а не классическим КТ.
@AlexanderSKing Я не эксперт, поэтому мне придется оставить то, что я уже сказал. Я внимательно прочитал статью из SEP plato.stanford.edu/entries/church-turing . Слово «человек» встречается 48 раз. Трудно не прочитать все это и не прийти к выводу, что либо КТ очень плохо сформулирован; или же это на самом деле утверждение о мире.
@ user4894: мы должны согласиться не согласиться. см. р. статью Соара об истории концепции вычислимости на people.cs.uchicago.edu/~soare/History для опровержения вашего утверждения одним из ведущих ученых в этой области.
@Dave См. мой ответ Александру С. Кингу. В статье SEP о КТ слово «человек» используется 48 раз. Я понимаю, что КТ говорит о человеке, механически выполняющем алгоритм; но все же, это всегда человек. С таким определением трудно представить даже платоника, заявляющего, что существует эффективная процедура без людей. В платоновском царстве абстракций может существовать алгоритм, но нет человека, который мог бы его выполнить. КТ сильно отличается по своему характеру от математической теоремы. Но я не эксперт, так что ничего добавить к сказанному не могу.

Тезис Черча-Тьюринга является недоказуемым тезисом, а не теоремой, потому что это утверждение о том, что наше неформальное, нетеоретическое понимание того, что считается эффективно вычислимым, полностью схвачено тем, что поддается вычислению с помощью машины Тьюринга или, что то же самое, , общерекурсивной функцией. Термин «гиперкомпьютер» используется для обозначения вычислительного устройства, которое может вычислять вещи, которые не поддаются вычислению по Черчу-Тьюрингу, поэтому другой способ выразить тезис состоит в том, что это утверждение об отсутствии гиперкомпьютеров.

Утверждение о том, что гиперкомпьютеров не существует, нельзя опровергнуть, но такое отрицательное утверждение можно поддержать (но не доказать), если мы приложим все усилия, чтобы разработать гиперкомпьютер и показать, что он неосуществим. Было предложено несколько теоретических моделей гипервычислений, но ни одна из них не оказалась реально реализуемой.

Можно пойти еще дальше и утверждать, что для реализации гиперкомпьютера он должен работать в соответствии с законами физики, а с учетом того, что мы знаем о физике в настоящее время, это по своей сути неправдоподобно. Гиперкомпьютер должен быть основан на странной физике: даже более странной, чем квантовая механика, поскольку квантовые компьютеры согласуются с Черчем-Тьюрингом. Идеальный аналоговый компьютер потенциально мог бы быть гиперкомпьютером, но он должен был бы иметь возможность обрабатывать действительные числа с бесконечной точностью, что не согласуется с картиной Вселенной, которую предлагает нам КМ.

Поэтому вполне разумно признать, что тезис Черча-Тьюринга верен, и основывать на нем научную работу, даже если мы не можем это доказать.

«Термин гиперкомпьютер используется для обозначения вычислительного устройства, которое может вычислять вещи, которые не поддаются вычислению по Черчу-Тьюрингу». Машина Тьюринга. это иногда называют «вводом-выводом».
Я не уверен, почему вы сделали этот комментарий. Машины Тьюринга (или рекурсивные функции, если уж на то пошло) могут иметь ввод и вывод. Гиперкомпьютеры — это предполагаемые теоретические устройства, которые могут вычислять то, что невозможно вычислить на машинах Тьюринга.
Машины Тьюринга ничего не делают. это хорошо известно.
Вы используете ввод/вывод странным образом. Начальное состояние ленты ТМ обычно считается ее входом, а конечное состояние — ее выходом. Сам Тьюринг использовал термины «ввод» и «вывод» таким образом для описания работы ТМ, и с тех пор это сделали другие. Было бы трудно объяснить концепции универсальной ТМ или проблемы остановки без ссылки на входные данные...
Если вы имеете в виду что-то более сильное, например способность машины позволять внешнему процессу перезаписывать свою ленту во время выполнения вычислений, то такая машина действительно не будет ТМ, но все равно будет весьма спорно утверждать что она не эквивалентна никакой ТМ. Таким образом, сказать, что «машины Тьюринга не выполняют ввод-вывод» в этом сильном смысле, верно, но из этого не следует, что у вас «есть устройство, которое регулярно вычисляет вещи, которые не могут быть вычислены ТМ».
Я имел в виду io в обычном смысле программирования. printf не является вычислимой функцией Тьюринга. см., например, работу Питера Вегнера по интерактивным вычислениям cs.brown.edu/~pw
Я знаком с работами Вегнера, но до сих пор считаю его утверждения об опровержении тезиса Черча-Тьюринга весьма спорными. Похоже, они не достигли какого-либо консенсуса в сообществе теории вычислимости. В разделе «Теоретическая информатика» Stack Exchange есть запись, посвященная этой проблеме: cstheory.stackexchange.com/questions/12377/…
ха, я как раз читал эту тему! На самом деле я думаю, что robert soare - лучшая ссылка, см. esp. его статья об истории вычислимости на people.cs.uchicago.edu/~soare/History
Научность тезиса Черча-Тьюринга
СпросиСетьПолитика конфиденциальности1y, 0v