Почему машина Тьюринга является популярной моделью вычислений?

68

Я студент бакалавриата. Я понимаю, как Тьюринг придумал свою абстрактную машину (моделирующую человека, выполняющего вычисления), но мне кажется, что это неуклюжая, не элегантная абстракция. Почему мы рассматриваем «ленту», а машинная голова пишет символы, меняя состояние, смещая ленту назад и вперед?

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

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

Редактировать :

Прочитав несколько ответов, я понял, что меня смущает в машине Тьюринга то, что она не кажется минимальной. Разве каноническая модель вычислений не должна явно передавать суть вычислимости?

Кроме того, на случай, если неясно, я знаю, что DFA не являются полными моделями вычислений.

Спасибо за ответы.

Alex
источник
2
Надеюсь, будущие занятия помогут уточнить.
Юваль Фильмус
19
Возможно, вы найдете лямбда-исчисление как более естественную модель вычислений. Это то, на чем основано функциональное программирование.
Бакуриу
4
На самом деле, я собираюсь закончить. Курс высшего уровня, который я выбрал, включающий теорию автоматов, остановился на машинах Тьюринга, хотя в них упоминалась эквивалентность между различными моделями вычислений. Я даже сделал свою справедливую долю, по праву говоря, базового «программирования» ТМ. ТМ, однако, всегда меня раздражала. Это не казалось "минимальным"; это не раскрыло мне суть вычислений.
Алекс
4
« какая-то физическая система, соответствующая входной строке » - как будет выглядеть это соответствие? Машина Тьюринга - довольно простая, но мощная формальная модель именно для такой вещи.
Берги
2
Машины Тьюринга действительно изменяются детерминированно, основываясь исключительно на исходном состоянии (если вы имеете в виду конфигурацию). Так что с этим не так?
user23013

Ответы:

72

Ну, DFA - это просто машина Тьюринга, которой разрешено только двигаться вправо, и которая должна принимать или отклонять, как только в ней заканчиваются вводимые символы. Так что я не уверен, что можно сказать, что DFA - это естественно, а машина Тьюринга - нет.

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

Хорошо, хорошо, вы говорите (я надеюсь!), Но мы больше не в 30-х годах, так почему мы до сих пор используем это? Здесь я не думаю, что есть какая-то конкретная причина. Преимущество машин Тьюринга в том, что они достаточно просты, и мы неплохо доказываем, что с ними происходит. Хотя формальное указание программы Тьюринга для выполнения какой-то конкретной задачи очень утомительно, после того, как вы сделали это несколько раз, у вас есть разумное представление о том, что они могут сделать, и вам больше не нужно писать формальные спецификации. Модель также легко расширяется, чтобы включить другие естественные функции, такие как произвольный доступ к ленте. Так что это довольно полезная модель, которую мы хорошо понимаем, и у нас также есть довольно хорошее понимание того, как они соотносятся с реальными компьютерами.

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

Дэвид Ричерби
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Жиль "ТАК - перестань быть злым"
56

Вы задаете несколько разных вопросов. Позвольте мне кратко ответить на них один за другим.

Что такого важного в модели машины Тьюринга?

λ

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

Обычная компьютерная наука учит машины Тьюринга как определение вычислимости, а затем использует их также для изучения теории сложности. Но алгоритмы анализируются в отношении более реалистичной модели, известной как машина ОЗУ, хотя эта проблема обычно скрывается за секретом для cognoscenti.

Разве DFA не лучшая модель?

Это была первоначальная мотивация знаменитой статьи Рабина и Скотта «Конечные автоматы» и проблемы их решения:

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

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

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

Не слишком ли ограничена модель машины Тьюринга?

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

Юваль Фильмус
источник
17

Основополагающее значение имеет идея об эквивалентности по Тьюрингу. Точная модель не важна, если она эквивалентна по Тьюрингу. Но лучше использовать более простую модель, чтобы вы могли легче доказать эквивалентность другим моделям.

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

Существуют и другие модели, такие как лямбда-исчисление и грамматика (переписывание строк). Но проще определить временные и пространственные ограничения в машине Тьюринга. Вы также можете использовать язык программирования, такой как Brainfuck, но это требует ненужной работы, например, для переопределения символов, чтобы иногда получить логически тривиальную модификацию.

Таким образом, машина Тьюринга показалась мне вполне подходящей, если вам нужно выучить одну модель для всего. Но если вы все равно собираетесь изучать несколько моделей, я не вижу ничего плохого в том, чтобы выучить лямбда-исчисление для идеи эквивалентности по Тьюрингу, Brainfuck для доказательства эквивалентности по Тьюрингу других моделей и практических языков программирования (лучше с доступным стеком и без скрытых переменных). для ограничений времени / пространства, и рассматривайте машину Тьюринга только как инструмент, доказывающий, что эти вещи эквивалентны, если никто не удосужился найти способ обойти это. Это естественно случается, если вы сначала не начали изучать основную теорию, а сделали это только тогда, когда нашли ее полезной.

user23013
источник
1
По сути, все настоящие современные процессоры - это зарегистрированные машины с оперативной памятью. Даже микроконтроллеры или игрушечные архитектуры с одним регистром аккумулятора обычно имеют какой-то отдельный адресный регистр, в который вы можете загружать указатели, вместо того, чтобы быть чистой машиной накопителя. Но реальное оборудование имеет адреса фиксированного размера и, следовательно, не является полным по Тьюрингу. IDK, если модель «машина регистра» широко используется в теоретической CS, но это то, как язык ассемблера работает в реальной жизни, и это может быть полезно понять для анализа производительности, потому что все компилируется в asm.
Питер Кордес
14

Я хотел бы ответить на эту часть вопроса, добавленную в редактировании:

«Разве каноническая модель вычислений не должна явно передавать суть вычислимости?»

TTT

Это одна из сущностей вычислимости: каково бы ни было общее понятие вычислимости, должна быть одна машина, которая делает все это. Это именно то, что делает универсальная машина Тьюринга. Это также то, что делают современные компьютеры (при условии физически нереалистичной идеализации обладания бесконечной памятью).

Еще один способ выразить это, который напрямую касается вашей озабоченности тем, что машины Тьюринга не являются минимальными, состоит в том, что они настолько минимальны, насколько они могут быть, при условии, что они описывают общее понятие вычислимости, для которого существует универсальная машина.

Ли Мошер
источник
Спасибо, что напомнили мне об универсальной машине. Я вижу, как это подразумевает «полное» вычисление.
Алекс
5

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

Они специально не созданы для того, чтобы «делать» что-либо. Они не должны быть минимальными, они не должны быть удобными для работы.

Это просто модель машины, которую вы могли бы построить, которая была бы такой же выразительной и мощной, как любая другая машина, которую вы когда-либо могли построить в физической вселенной (насколько мы знаем сегодня).

Они были определены Тьюрингом такими, какими они являются по следующим основным причинам:

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

Было бы возможно выбрать другой язык? Точно! Можно было использовать любой из известных нам тьюринговых языков. Но было бы гораздо сложнее построить теоретическую основу на более сложной машине.

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

Anoe
источник
Согласитесь по всем пунктам. Популярность только возможно относительно более неясных моделей как машины Thue и Lambda исчисление и материал Эмиля Поста.
luser droog
Извините, но вы упускаете очень важный момент, который могли бы испортить другие языки. Машина Тьюринга определяет, что вы можете вычислить. Любые другие языки будут ограничивать вопрос о том, как вы можете его вычислить, что вряд ли сможет доказать, что вы можете вычислять или нет.
согнуло
Если машины Тьюринга должны быть целью сокращения для других моделей, почему они не должны быть минимальными?
Берги
@ Бент, я признаю, что я не совсем понимаю, что вы пытаетесь сказать, в дополнение к тому, что я упомянул: «Но было бы намного сложнее построить теоретическую основу на более сложной машине». (то есть на реальном языке программирования, который мы знаем и используем).
AnoE
Под популярностью я имел в виду то, что используется в Теоретической CS. Опять же, это была единственная модель, которую я изучил (хотя я думаю, что подвергся небольшому воздействию лямбда-исчисления). Я просто удивился, почему, возможно, с педагогической точки зрения, этому всегда учат первым. Я вижу, как практичность этого оправдывает.
Алекс
5

Почему он популярен, может быть, самый популярный? Вы должны помнить, что Тьюринг изобрел эту «машину» за много лет до появления электронных компьютеров. ТМ работает с бумагой, ручкой, резиной и, что не менее важно, человеческим мозгом. Таким образом, каждый может выполнить «вычисления» с этой машиной. Каждый означает человека, который никогда не изучал компьютеры, программируя языки. Это просто в использовании. Когда вы думаете об этом, вы обнаруживаете парадокс: эта машина представляет собой сборку почти ничего, но вы можете управлять всем. На мой взгляд, парадокс «почти ничего / против / всего» является причиной его популярности. Я хотел бы заметить, что TM не объясняет рекурсию в явном виде, а TM имеет дело только с «прыжком». Эта особенность (явно говоря о рекурсии) может быть источником головной боли для новичков, например, в лямбда-исчислении концепция Y-комбинатора почти не понятна; Точнее, ТМ пользуется популярностью потому, что парадокс «почти ничего / против / всего» без головной боли рекурсии.

user88464
источник