Что значит быть полным по Тьюрингу?

34

Я вижу, что большинство определений того, что должно быть полным по Тьюрингу, в некоторой степени тавтологично. Например, если вы Google «что значит быть полным по Тьюрингу», вы получите:

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

Хотя очень четко определено, являются ли разные системы полными по Тьюрингу или нет, я не видел объяснения того, каковы последствия / последствия того, что полнота по Тьюрингу завершена.

Что может сделать машина Тьюринга, если не существует машины Тьюринга, которая могла бы выполнить ту же задачу? Например, компьютер может выполнять простые вычисления, например (1+5)/3=?, но обычный калькулятор также может их выполнять, что, если я прав, не является полным по Тьюрингу.

Есть ли способ определить возможности машины Тьюринга, не говоря «возможность имитировать другую машину Тьюринга»?

sashoalm
источник
31
Найти определение «машина Тьюринга». Не существует кругового определения, поскольку машина Тьюринга не определяется как «способная имитировать другую машину Тьюринга» - это полностью разработанный теоретический компьютер (в основном, бесконечный ленточный конечный автомат). Вы просто смешиваете «Тьюринг-полный» и «Тьюринговый аппарат». Насколько я знаю, мы до сих пор не знаем ни одного алгоритма, который не может работать на машине Тьюринга, но это может быть только мое собственное невежество.
Луаан
2
@Luaan Тезис Церковного Тьюринга согласился бы с вами.
Брайан Маккатон
«Есть ли способ определить возможности машины Тьюринга». Конечно. Теория состоит в том, сколько места и времени требуется для решения алгоритмов на машинах Тьюринга (L, NL, P, NP, PSPACE и т. Д.), И есть также проблемы, которые не могут быть решены (которые обычно могут быть решены путем сокращения до другие неразрешимые проблемы). Одним из примеров проблемы, которая не может быть решена машинами Тьюринга, является проблема остановки.
Милли Смит
Когда речь идет о теории CS (или любой другой), всегда лучше прочитать книгу по теме, чем гуглить и прочитать несколько постов в блоге по теме, которые во многих случаях написаны людьми, которые не совсем понимают тему самих себя. Одна хорошая книга сэкономит ваше время, предоставит вам более широкую картину и лучшее понимание.
Божидар Сиканджич
Функция Аккермана является ярким примером того, что машина Тьюринга может вычислить, но более ограниченная модель вычислений ( примитивная рекурсия ) не может.
Звол

Ответы:

13

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

Но что это значит?

Что значит быть полным по Тьюрингу?

Есть ли способ определить возможности машины Тьюринга, не говоря «возможность имитировать другую машину Тьюринга»?

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

(NB: чтобы выяснить, почему это «неформально», посмотрите тезис Черча-Тьюринга, который идет в том же духе, с более сложной формулировкой; будучи тезисом, он может или не может быть правильным, хотя. Спасибо @DavidRicherby за указывая на это маленькое упущение в комментарии.)

«Алгоритм» означает то, что мы обычно понимаем как компьютерный алгоритм сегодня; т. е. ряд дискретных шагов, манипулирующих хранилищем, со смешанной некоторой управляющей логикой. Однако он не похож на машину Oracle, т. е. не может «угадывать».

Пример для практического не-тс языка

Если вы запрограммировали себя, вы, вероятно, знаете регулярные выражения, используемые для сопоставления строк с каким-либо шаблоном.

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

Например (и это, безусловно, раздражало многих программистов в реальных реальных приложениях), теоретически и практически невозможно создать регулярное выражение, соответствующее языку программирования или документу XML: для регулярного выражения невозможно найти структуру блока ( do ... endили { ... }на языках; открывающие и закрывающие теги в XML-документах), если им разрешено быть сколь угодно глубокими. Если там есть предел, например, у вас может быть только 3 уровня «рекурсии», тогда вы можете найти регулярное выражение; но если это не ограничено, то это не пойдет.

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

мотивация

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

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

До бесконечности

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

... и дальше

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

Anoe
источник
«Неформально говоря, полная целостность по Тьюрингу означает, что ваш механизм может запускать любой алгоритм, о котором вы только могли подумать». Ну, это зависит от принятия тезиса Черча-Тьюринга, в котором говорится, что машины Тьюринга могут реализовать любой алгоритм, который вы можете придумать. Или, в качестве альтернативы, вы можете принять машины Тьюринга в качестве определения алгоритма, и в этом случае неформальное утверждение является просто неформальной версией «может имитировать любую машину Тьюринга» (что не так уж плохо; просто наблюдение).
Дэвид Ричерби,
У меня сложилось впечатление, что ОП спрашивает об интуитивном понимании того, что значит быть завершенным. Следовательно, этот вид легкомысленного, не теоретического компьютерного ответа. Спасибо за указание на это, я включу это в ответ. @DavidRicherby
AnoE
Благодарность! Вот такой ответ я искал. Я думал о проблеме остановки и о том, как языки с простыми ограниченными циклами for предсказуемы (они всегда останавливаются) - и, следовательно, не являются полными по Тьюрингу. Я думал, может быть, быть полным по Тьюрингу означает быть потенциально непредсказуемым в некотором роде (является ли хаотичным правильный термин для этих функций?)
sashoalm
@sashoalm, рад, что тебе нравится ответ. Нет, непредсказуемость на самом деле не влияет на проблему. Ограниченный цикл for (как не-tc) также является хорошим примером. Фактически, еще одним хорошим примером для простого (и более реального) языка tc был бы тот, который имеет только переменные и (неограниченные) while- этого уже достаточно, чтобы быть tc. (Не) ограниченность структуры управления является одним из ключевых элементов.
AnoE
38

Это не тавтологически.

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

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

aб

Есть ли способ определить возможности машины Тьюринга, не говоря «возможность имитировать другую машину Тьюринга»?

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

Дэвид Ричерби
источник
19
Я думаю, что OP смешивает машину Тьюринга и Тьюринга в комплекте. На самом деле он ищет определение машины Тьюринга; Ваше последнее предложение является ответом. en.wikipedia.org/wiki/Turing_machine поможет.
JollyJoker
Так что же может сделать машина Тьюринга? Например, если я хотел доказать, что что-то может эмулировать машину Тьюринга, какой минимальный набор поведений я должен продемонстрировать, что моя машина тоже может это делать?
Акшат Махаджан,
2
Не берите в голову - я решил, что достаточно продемонстрировать, что язык может имитировать работу машины Тьюринга, чтобы доказать, что она полная по Тьюрингу.
Акшат Махаджан,
17

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

Компьютер полон по Тьюрингу, если он может решить любую проблему, которую может решить Excel.

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


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

Однако можно определить нетривиальные понятия задач Тьюринга, например:

LAеaAе(a)L

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

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

Юваль Фильмус
источник
«К сожалению, ответ зависит от машины Тьюринга», - я отредактировал свой вопрос, потому что он не был ясен. Вы можете выбрать любую машину без тьюринга, если она может выполнять задачу, оставаясь при этом не полной по Тьюрингу.
sashoalm
5
Excel is also Turing-complete.- только если вы можете дать Excel бесконечную память. Excel ограничен 1 048 576 строками и 16 384 столбцами, что практически бесконечно.
MattClarke
5
@MattClarke: Да, но, к тому же, ни одна из построенных систем не является полной по Тьюрингу.
Эмиль
3
@Emil: точно, и важно, чтобы ученики CS различали возможности вычислительных моделей и возможности реальных машин. Те из нас, кто неоднократно сталкивался с физическими ограничениями наших реальных машин, конечно, легко находят это различие. Таким образом, мы знаем, как определить неограниченную версию вычислительной модели Excel и что она будет полной по Тьюрингу. Хотя на самом деле выписать это определение довольно сложно.
Стив Джессоп
4
@SteveJessop Физические ограничения машин? Как кто-нибудь может ударить такую ​​вещь? 640к хватит на всех!
Дэвид Ричерби
4

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

μ

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

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

быстрая сортировка
источник
0

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

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

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

alanf
источник