Насколько я понимаю, модель Тьюринга стала «стандартом» при описании вычислений. Мне интересно знать, почему это так - то есть, почему модель ТМ стала более широко используемой, чем другие теоретически эквивалентные (насколько мне известно) модели, например μ-Рекурсия Клини или Лямбда-исчисление (я понимаю что первое появилось только позже, а второе изначально не было разработано специально как модель вычислений, но оно показывает, что альтернативы существовали с самого начала).
Все, о чем я могу думать, - это то, что модель TM более точно представляет компьютеры, которые у нас есть, чем ее альтернативы. Это единственная причина?
Ответы:
Это кажется верным в контексте (некоторых областей) информатики, но не в целом.
Одна из причин связана с церковным тезисом. Основная причина в том, что некоторые эксперты, такие как Годель, не думали, что аргументы, что предыдущие / другие модели вычислений точно отражают интуитивную концепцию вычислений, были убедительными. Есть разные аргументы, у Черча были некоторые, но они не убедили Годеля. С другой стороны, анализ Тьюринга был убедительным для Годеля, поэтому он был принят в качестве модели для эффективных вычислений. Эквивалентность между различными моделями доказана позже (я думаю, что Клини).
Некоторые ресурсы для дальнейшего чтения:
Роберт И. Соаре имеет ряд статей об истории этих разработок, лично мне нравится статья в «Руководстве по теории вычислимости». Вы можете узнать больше, проверив ссылки в этом документе.
Еще один хороший ресурс - статья Нила Иммермана о вычислимости, посвященная СЭП, см. Также тезис Черча-Тьюринга, опубликованный Б. Джеком Коуплендом.
Гёделя собрание сочинений содержит много информации о его взглядах. Специально введения в его статьи чрезвычайно хорошо написаны.
« Метаматематика » Клини - очень хорошая книга.
Наконец, если вы все еще не удовлетворены, проверьте архивы списка рассылки FOM , и если вы не можете найти ответ в архиве, отправьте электронное письмо в список рассылки.
источник
Я хотел бы ослабить утверждение, что ТМ являются основной моделью вычислений или, по крайней мере, указывают на другое измерение вопроса. Очевидно, что ТМ доминируют в более сложных и алгоритмически ориентированных частях компьютерной науки, но в теории и практике языка программирования они не особенно доминируют. Для этого есть различные причины, но, возможно, наиболее важным является то, что ТМ или программы, работающие на ТМ (в отличие, например, от лямбда-исчислений или процессов-исчислений), не строятся алгебраическим образом. Это затрудняет разработку теорий типов, которые были основой теории языков программирования.
источник
Одна из приятных особенностей машин Тьюринга заключается в том, что они работают со строками вместо натуральных чисел или лямбда-выражений, поскольку входные и выходные данные многих задач могут быть естественно сформулированы как строки. Я не знаю, считается ли это «исторической» причиной или нет.
источник
Помимо того факта, что машины Тьюринга являются убедительной моделью вычислений на бумаге и пером («интуитивное представление о вычислениях»), я думаю, что они обладают рядом функций, которые часто полезны, особенно при доказательстве теорем о них:
источник
Он был первым, кто оказал влияние и, таким образом, был установлен, особенно в теории сложности. Это слабая причина, но люди работают таким образом. Сначала мы работаем над старыми открытыми проблемами, а не объявляем новые.
источник