Полное Тьюринга?

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

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

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

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

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

обновление: вы можете узнать больше на моем блоге: "JavaScript-Это Turing Complete" - Объяснил

с Википедия:

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

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

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

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

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

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

машина Тьюринга может принимать решения на основе того, что она видит в памяти - 'язык', который поддерживает только +,-,* и / on integers не является полным Тьюрингом, потому что он не может сделать выбор на основе его ввода, но машина Тьюринга может.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я настоятельно рекомендую аннотированный Тьюринг

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

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

Как

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

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

но C++ может это сделать, и может сделать любую проблему. Так оно и есть.