Есть ли физическая аналогия с машиной Тьюринга?

Недавно в классе CS я познакомился с машиной Тьюринга.

После урока я потратил более 2 часов, пытаясь выяснить, какова связь между лентой и машиной.

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

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

Может ли кто-нибудь привести лучший пример, опираясь на реальность, чтобы охватить основные функции этой гипотетической концепции?

Машины Тьюринга являются одной из «оригинальных» полных по Тьюрингу вычислительных моделей, наряду с исчислением и рекурсивно определенными рекурсивными функциями. В настоящее время во многих областях теоретической информатики используется другая модель - машина ОЗУ, которая намного ближе к реальным компьютерам. Поскольку обе модели являются p-эквивалентными (они имитируют друг друга с максимально полиномиальным раздувом), с точки зрения таких вопросов, как P против NP, обе модели эквивалентны.$\lambda$

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

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

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

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

Ответ @jkff уместен, отметив, что машина Тьюринга предназначена в качестве теоретического устройства для математической цели изучения вычислимости и доказуемости (возникающей фактически в контексте проблемы Гильберта Entscheidungsproblem ). Но это не совсем точно в причинах выбора простого формализма.

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

Важность наличия простой модели гораздо больше зависит от ее использования, чем от определения ее свойств (например, проблемы остановки, если взять пример, приведенный @jkff).

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

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

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

Однако, когда мы хотим доказать положительные результаты, такие как наличие алгоритма для решения какой-то данной проблемы, TM слишком упрощенное устройство. Гораздо проще рассмотреть расширенные модели режима, такие как компьютер с ОЗУ или компьютер с ассоциативной памятью , или одна из многих других моделей, или даже просто один из многих языков программирования.

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

Другими словами, модель TM часто слишком упрощена для разработки и изучения алгоритмов (положительные результаты) и часто слишком сложна для изучения вычислимости (отрицательные результаты).

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

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

Представьте новичка в геометрии, спрашивающего:

Есть ли физическая аналогия с треугольником?

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

Что бы вы ответили?

Вы можете сказать, что эти вопросы показывают два фундаментальных заблуждения о треугольниках:

1. «Треугольники чисто гипотетические». Неправильно! Хотя они являются математическими объектами, платоновскими идеалами и гипотетическими в этом смысле, треугольники реальны : мы можем построить их в реальном мире. Конечно, то, что мы строим, никогда не будет идеальным треугольником, но наша математическая теория о них действительно применима к реальному миру, законы, которые мы можем вывести, применимы к фигурам в реальном мире, теория может быть использована в качестве основы для проектирования, конструирование и измерение форм в реальном мире; это причина, по которой теория была разработана в первую очередь.
2. «Треугольники бесполезны, потому что они не описывают формы, которые мы обычно используем».Неправильно! Описание реальных форм, которые вы найдете в реальном мире, не является их целью. Если весь ваш офис или гостиная не содержат ни одного треугольника, это не означает, что концепция треугольника нереальна или устарела, и ее лучше заменить чем-то другим. Их основная цель - элементарная конструкция, из которой в принципе могут быть построены все более сложные формы, и поэтому мы можем вывести законы, применимые к фигурам в целом. Рассуждение о треугольниках позволяет нам рассуждать о формах в целом. Ваша гостиная подчиняется тем же законам, которые мы вывели для треугольников, и наши знания этих законов были использованы, прямо или косвенно, для ее построения. В гостиной, вероятно, нет ни одного треугольника, не говоря уже о идеальном, но нас не волнует нахождение там треугольников; мы можем. тем не менее, составьте описание фигур, сопоставив их с треугольниками, и это - триангуляция - популярное и полезное занятие. Таким образом, треугольники являются строительными блоками, которые помогают нам думать о формах в целом.

То же самое верно для машин Тьюринга.

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

Итак, для полноты картины:

1. «Машины Тьюринга чисто гипотетические». Неправильно! В то время как они являются математическими сущностями, платоновскими идеалами и гипотетическими в этом смысле, машины Тьюринга реальны : мы можем реально построить их в реальном мире. Конечно, то, что мы создаем, никогда не будет совершенной машиной Тьюринга, но наша математическая теория о них действительно применима к реальному миру, законы, которые мы можем вывести, применимы к вычислительным устройствам в реальном мире, теория может быть использована в качестве основы для проектирование, конструирование и измерение вычислительных устройств в реальном мире; это причина, по которой теория была разработана в первую очередь.
2. «Машины Тьюринга бесполезны, потому что они не описывают вычислительные устройства, которые мы обычно используем».Неправильно! Описание реальных вычислительных устройств, которые вы найдете в реальном мире, не является их целью. Если в вашем бэк-офисе или студии домашних развлечений нет ни одной машины Тьюринга, это не значит, что концепция машины Тьюринга нереальна или устарела, и ее лучше заменить чем-то другим. Их основное предназначение - элементарная конструкция, из которой в принципе могут быть построены все более сложные вычислительные устройства, и поэтому мы можем вывести законы, применимые к фигурам в целом. Рассуждения о машинах Тьюринга позволяют нам рассуждать об вычислительных устройствах в целом. Ваше компьютерное оборудование и программное обеспечение подчиняются тем же законам, которые мы разработали для машин Тьюринга, и наши знания этих законов использовались, прямо или косвенно, для их построения, даже если они, вероятно, не в них нет ни одной машины Тьюринга. Это законы, которые нас интересуют.

Физическая аналогия, которую, похоже, имел в виду Тьюринг, - это компьютер, решающий проблемы с карандашом, бумагой и ластиком. Вы должны понимать, что в 1936 году «компьютер» был человеком, нанятым для вычислений. Конечно, в 1936 году большинство компьютеров использовали бы добавляющие машины, но Тьюринг не упоминает об этом, поскольку они несущественны. Вот что он говорит в отношении ленты, пытаясь оправдать, что «вычислимые» числа [т.е. те, которые машина Тьюринга могла бы вычислить] включают в себя все числа, которые, естественно, будут считаться вычислимыми ».

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

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

Для получения дополнительной информации см. Об вычислимых числах с приложением к проблеме entscheidungs , особенно разделы 1 и 9.

У @jkff есть идея the Turing Machine is modeled on the idea of a human with a pen and paperне совсем правильная. Но есть много ситуаций, когда это можно считать правильным.

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

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

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

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

Если вы хотите получить хороший ответ на свой вопрос, то, я думаю, Юваль Фильмус ответил на него хорошо. Используйте модель RAM. Придерживаться.