Исторические причины принятия машины Тьюринга в качестве основной модели вычислений.

44

Насколько я понимаю, модель Тьюринга стала «стандартом» при описании вычислений. Мне интересно знать, почему это так - то есть, почему модель ТМ стала более широко используемой, чем другие теоретически эквивалентные (насколько мне известно) модели, например μ-Рекурсия Клини или Лямбда-исчисление (я понимаю что первое появилось только позже, а второе изначально не было разработано специально как модель вычислений, но оно показывает, что альтернативы существовали с самого начала).

Все, о чем я могу думать, - это то, что модель TM более точно представляет компьютеры, которые у нас есть, чем ее альтернативы. Это единственная причина?

Evan
источник
1
хотя они не имеют непосредственного отношения к одной и той же теме, вопросы cstheory.stackexchange.com/questions/625/… и cstheory.stackexchange.com/questions/1117/… исследуют отношения между ТМ и калькуляцией и имеют некоторые исторические элементы. λ
Суреш Венкат
Да, я видел их. Я довольно хорошо понимаю буквальную историю различных теорий, но меня больше интересуют события, которые со временем привели к текущим «предпочтениям» в этой области, если хотите.
Эван
2
На самом деле есть модели, которые (возможно) ближе к реальным компьютерам, см. Этот вопрос . Как правило, лучшая модель зависит от потребностей, и они отличаются от одной области к другой.
Каве

Ответы:

46

Это кажется верным в контексте (некоторых областей) информатики, но не в целом.

Одна из причин связана с церковным тезисом. Основная причина в том, что некоторые эксперты, такие как Годель, не думали, что аргументы, что предыдущие / другие модели вычислений точно отражают интуитивную концепцию вычислений, были убедительными. Есть разные аргументы, у Черча были некоторые, но они не убедили Годеля. С другой стороны, анализ Тьюринга был убедительным для Годеля, поэтому он был принят в качестве модели для эффективных вычислений. Эквивалентность между различными моделями доказана позже (я думаю, что Клини).

λμ

μλ, Также см. Эти работы Вигго Столтенберга-Хансена и Джона В. Такера I , II .)

Некоторые ресурсы для дальнейшего чтения:

Роберт И. Соаре имеет ряд статей об истории этих разработок, лично мне нравится статья в «Руководстве по теории вычислимости». Вы можете узнать больше, проверив ссылки в этом документе.

Еще один хороший ресурс - статья Нила Иммермана о вычислимости, посвященная СЭП, см. Также тезис Черча-Тьюринга, опубликованный Б. Джеком Коуплендом.

Гёделя собрание сочинений содержит много информации о его взглядах. Специально введения в его статьи чрезвычайно хорошо написаны.

« Метаматематика » Клини - очень хорошая книга.

Наконец, если вы все еще не удовлетворены, проверьте архивы списка рассылки FOM , и если вы не можете найти ответ в архиве, отправьте электронное письмо в список рассылки.

Кава
источник
Пожалуйста, дайте мне знать, если у меня что-то не так.
Каве
1
Вау, это отличная информация. Спасибо за ресурсы, я проверю их (я планировал читать Метаматематику - я подниму его до очереди).
Эван
Пожалуйста, надеюсь, я не ошибаюсь. :)
Каве
Был недавний разговор Роберта Соарой в INI. Насколько я понимаю, главная причина перехода к модели Тьюринга и вычислимости с рекурсивных функций и теории рекурсии для него заключается в следующем: трудно понять и работать в теории рекурсии до такой степени, что никто не понимал, что происходит, кроме В некоторых случаях изменение вычислимости значительно облегчило понимание и оживило область.
Каве
19

Я хотел бы ослабить утверждение, что ТМ являются основной моделью вычислений или, по крайней мере, указывают на другое измерение вопроса. Очевидно, что ТМ доминируют в более сложных и алгоритмически ориентированных частях компьютерной науки, но в теории и практике языка программирования они не особенно доминируют. Для этого есть различные причины, но, возможно, наиболее важным является то, что ТМ или программы, работающие на ТМ (в отличие, например, от лямбда-исчислений или процессов-исчислений), не строятся алгебраическим образом. Это затрудняет разработку теорий типов, которые были основой теории языков программирования.

Мартин Бергер
источник
2
Кроме того, программы ТМ, также известные как таблицы переходов, не очень удобочитаемы.
Рафаэль
13

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

Цуёси Ито
источник
13

Помимо того факта, что машины Тьюринга являются убедительной моделью вычислений на бумаге и пером («интуитивное представление о вычислениях»), я думаю, что они обладают рядом функций, которые часто полезны, особенно при доказательстве теорем о них:

  • их легко описать формально и имеют простую операционную семантику;
  • легко дать конкретное определение их времени и сложности пространства;
  • ТМ с полиномиальными издержками могут моделировать более реалистичные (и сложные) модели электронных компьютеров, таких как машины с произвольным доступом, и наоборот.
Антонио Э. Поррека
источник
Иногда возможность описания, кажется, препятствует полезности ТМ, поскольку описания могут быстро перерасти в простые объяснения на английском языке, если вы не будете осторожны (по крайней мере, если я не буду осторожен ... По общему признанию, я новичок).
Эван
Например, ваши причины не исключают регистрацию машин.
Рафаэль
Ну, это зависит от того, какое именно понятие «регистрационный компьютер» вы рассматриваете. Например, те, которые имеют только операции увеличения, уменьшения и перехода, не могут моделировать ТМ за полиномиальное время.
Антонио Э. Поррека
1
λλ
Я на стороне PL, но чистое лямбда-исчисление не является очевидной моделью арифметических вычислений (подумайте о функции предшественника). В лямбда-исчислении у вас меньше в определении, но требуется больше усилий, чтобы понять значение этого определения.
Blaisorblade
0

Он был первым, кто оказал влияние и, таким образом, был установлен, особенно в теории сложности. Это слабая причина, но люди работают таким образом. Сначала мы работаем над старыми открытыми проблемами, а не объявляем новые.

Рафаэль
источник
8
«Сначала мы работаем над старыми открытыми проблемами, а не объявляем новые». <- Я думаю, что, если что-нибудь, верно обратное, особенно в области, где старые вопросы чрезвычайно трудны. Например, сравнительно мало людей работают над сложностью схемы (хотя, возможно, их будет больше!). Люди должны работать над проблемами, которые они могут решить для публикации; это создает постоянный поток недавно объявленных решаемых задач.
Аарон Стерлинг
Я был немного поспешным в моей формулировке там. Я чувствую, что часто люди предпочитают придерживаться установленной модели, а не создавать новую (и доказывать ее основные свойства), если для этого нет непреодолимой причины. Это чувство может быть выключено, очевидно. В частности, конечно, есть люди, которые в первую очередь охотятся на модели.
Рафаэль
Ну, лямбда-исчисление пришло первым. Но Тьюринг показал, что машины Тьюринга точно моделируют основы человека, делающего вычисления; это было сделано только для лямбда-исчисления при доказательстве эквивалентности. Более того, эта эквивалентность верна только для вычислений первого порядка: cstheory.stackexchange.com/q/1117/989 - данных более высокого порядка на самом деле не существует на бумаге. Его даже не существует в памяти компьютера, но его можно идеально смоделировать.
Blaisorblade