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

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

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

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

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

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

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

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

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

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

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

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

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

Из википедии :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например :

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

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

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

Его можно завершить, если он может тестировать и ветвиться (имеет «если»)

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

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

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

Рулон пианино гарантированно останавливается каждый раз. Для ТМ такой гарантии нет. Это называется «проблема остановки».

Как сказал Вэйлон Флинн :

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

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

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

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

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