Что такое полный Тьюринг?

Question

Что означает выражение «полный Тьюринг»?

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

Answer 1

Вот краткое объяснение:

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

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

Иногда это шутка ... парень написал симулятор Turing Machine для vi, поэтому можно сказать, что vi - единственный вычислительный движок, когда-либо необходимый в мире.

Answer 2

Вот самое простое объяснение

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

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

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

Большинство современных языков программирования, таких как Java, JavaScript, Perl и т. Д., Полностью завершены, поскольку все они реализуют все функции, необходимые для запуска программ, такие как сложение, умножение, условие if-else, операторы return, способы хранения / извлечения / удаления данных. и т. д.

Обновление: вы можете узнать больше на моем блоге: "JavaScript завершен, Тьюринг завершен" - Объяснено

Answer 3

Из Википедия :

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

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

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

Answer 4

Неформальное определение

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

Вещи, которые могут сделать язык НЕ Тьюринг завершенным

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

Машина Тьюринга может работать вечно - Если бы мы взяли Java, Javascript или Python и удалили возможность выполнять какие-либо циклы, GOTO или вызов функции, это не было бы завершением Тьюринга, потому что он не может выполнить произвольное вычисление, которое никогда не заканчивается. Coq - это средство проверки теорем, которое не может выразить программы, которые не завершаются, поэтому оно не завершено по Тьюрингу.

Машина Тьюринга может использовать бесконечную память - Язык, который был в точности похож на Java, но прекратил бы работу, если бы он использовал более 4 ГБ памяти, не был бы завершен по Тьюрингу, поскольку машина Тьюринга может использовать бесконечное объем памяти. Вот почему мы не можем на самом деле собрать машину Тьюринга, но Java по-прежнему является полным языком Тьюринга, потому что язык Java не имеет ограничений, препятствующих использованию бесконечной памяти. Это одна из причин, почему регулярные выражения не являются полными по Тьюрингу.

Машина Тьюринга имеет оперативную память - язык, который позволяет работать с памятью только через операции push и pop в стеке, не будет завершен по Тьюрингу. Если у меня есть «язык», который читает строку один раз и может использовать память только путем выталкивания и извлечения из стека, он может сказать мне, есть ли у каждого ( в строке свой собственный ) позже нажмите, когда он видит (, и нажмите, когда он видит ). Тем не менее, он не может сказать мне, если каждый ( имеет свой собственный ) позже и каждый [ имеет свой собственный ] позже (обратите внимание, что ([)] соответствует этому критерию, но ([]] нет). Машина Тьюринга может использовать свою оперативную память для отслеживания () и [] по отдельности, но этот язык только со стеком не может.

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

Примеры тьюринговых полных языков

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

• Нетипизированное лямбда-исчисление
• Игра жизни Конвея
• Шаблоны C ++
• Пролог

Answer 5

По сути, полнота по Тьюрингу - это одно краткое требование, неограниченная рекурсия.

Даже не ограничен памятью.

Я думал об этом независимо, но здесь есть некоторое обсуждение утверждения. Мое определение LSP дает больше контекста.

Другие ответы здесь не определяют напрямую фундаментальную сущность полноты по Тьюрингу.

Answer 6

Turing Complete означает, что он по крайней мере такой же мощный, как Turing Machine . Это означает, что все, что может быть вычислено с помощью машины Тьюринга, может быть вычислено с помощью системы Turing Complete.

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

Answer 7

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

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

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

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

Answer 8

Что я понимаю простыми словами:

Завершение Тьюринга: Язык программирования / программа, которая может выполнять вычисления, является завершением Тьюринга.

Например:

1. Можете ли вы добавить два числа, используя Just HTML . (Ответ: « Нет », для выполнения добавления необходимо использовать JavaScript). Следовательно, HTML не является полным по Тьюрингу.

2. Такие языки, как Java, C ++, Python, Javascript, Solidity для Ethereum и т. Д., Являются Turing Complete, поскольку вы можете выполнять вычисления, например, добавляя два числа с использованием этих языков.

Надеюсь, это поможет.

Answer 9

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

Я очень рекомендую Аннотированную Тьюринг

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

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

Answer 10

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