Что такое полный Тьюринг?
Что означает выражение "полный Тьюринг"?
Можете ли вы дать простое объяснение, не вдаваясь в слишком много теоретических деталей?
16 ответов
Вот краткое объяснение:
Система Turing Complete означает систему, в которой может быть написана программа, которая найдет ответ (хотя и без гарантий относительно времени выполнения или памяти).
Итак, если кто-то скажет, что "моя новая вещь - Тьюринг Полная", это означает, что в принципе (хотя часто и не на практике) его можно использовать для решения любой вычислительной задачи.
Иногда это шутка... парень написал симулятор Turing Machine для vi, так что можно сказать, что vi - единственный вычислительный движок, когда-либо необходимый в мире.
Вот самое простое объяснение
Алан Тьюринг создал машину, которая может взять программу и запустить эту программу и показать некоторый результат. Но тогда ему пришлось создавать разные машины для разных программ. Поэтому он создал "Универсальную машину Тьюринга", которая может взять любую программу и запустить ее.
Языки программирования похожи на эти машины (хотя и виртуальные). Они берут программы и запускают их. Теперь язык программирования называется "завершением по Тьюрингу", если он может запускать любую программу (независимо от языка), которую машина Тьюринга может запускать, имея достаточно времени и памяти.
Например: допустим, есть программа, которая берет 10 чисел и добавляет их. Машина Тьюринга может легко запустить эту программу. Но теперь представьте себе, что по какой-то причине ваш язык программирования не может сделать то же самое дополнение, чем неполная машина Тьюринга. С другой стороны, если он может запустить какую-либо программу, например, универсальную машину Тьюринга, то выполнение Тьюринга завершено.
Большинство современных языков программирования, таких как Java, JavaScript, Perl и т. Д., Полностью завершены, поскольку в них реализованы все функции, необходимые для запуска программ, такие как сложение, умножение, условие if-else, операторы return, способы хранения / извлечения / удаления данных и т. Д.,
Обновление: вы можете узнать больше на моем блоге: "JavaScript завершается" - Объяснение
Неформальное определение
Полный язык Тьюринга - это язык, который может выполнять любые вычисления. Тезис Черча-Тьюринга утверждает, что любые выполнимые вычисления могут быть выполнены машиной Тьюринга. Машина Тьюринга - это машина с бесконечной оперативной памятью и конечной "программой", которая определяет, когда ей следует читать, записывать и перемещаться по этой памяти, когда она должна завершиться с определенным результатом и что она должна делать дальше. Ввод в машину Тьюринга помещается в ее память до ее запуска.
Вещи, которые могут сделать язык НЕ Тьюринг завершенным
Машина Тьюринга может принимать решения на основе того, что она видит в памяти - "язык", который поддерживает только +, -, *, а также / для целых чисел не является полным по Тьюрингу, потому что он не может сделать выбор на основе своего ввода, но машина Тьюринга может.
Машина Тьюринга может работать вечно - если бы мы взяли Java, Javascript или Python и удалили возможность выполнения любого вида цикла, GOTO или вызова функции, это не было бы завершением Тьюринга, потому что он не может выполнить произвольное вычисление, которое никогда не заканчивается Coq - это средство доказательства теорем, которое не может выразить программы, которые не завершаются, поэтому он не завершен по Тьюрингу.
Машина Тьюринга может использовать бесконечную память - язык, который был в точности похож на Java, но прекратил бы работу, если бы он использовал более 4 гигабайт памяти, не был бы завершен по Тьюрингу, потому что машина Тьюринга может использовать бесконечную память. Вот почему мы не можем на самом деле построить машину Тьюринга, но Java по-прежнему является полным языком Тьюринга, потому что у языка Java нет ограничений, не позволяющих ему использовать бесконечную память. Это одна из причин, почему регулярные выражения не являются полными по Тьюрингу.
Машина Тьюринга имеет оперативную память - язык, который позволяет работать с памятью только через push а также pop операции со стеком не будут завершены по Тьюрингу. Если у меня есть "язык", который читает строку один раз и может использовать память только путем извлечения и извлечения из стека, он может сказать мне, ( в строке есть своя ) позже, нажав, когда он видит ( и появляется, когда видит ), Тем не менее, он не может сказать мне, если каждый ( имеет свой ) позже и каждый [ имеет свой ] позже (обратите внимание, что ([)] соответствует этому критерию, но ([]] не). Машина Тьюринга может использовать свою оперативную память для отслеживания ()и []отдельно, но этот язык только со стеком не может.
Машина Тьюринга может имитировать любую другую машину Тьюринга. Когда машина Тьюринга получает соответствующую "программу", она может взять "программу" другой машины Тьюринга и смоделировать ее на произвольном входе. Если бы у вас был язык, которому было запрещено реализовывать интерпретатор Python, он не был бы завершен по Тьюрингу.
Примеры тьюринговых полных языков
Если ваш язык имеет бесконечную память с произвольным доступом, условное выполнение и некоторую форму повторного выполнения, вероятно, выполнение Тьюринга завершено. Существуют более экзотические системы, которые все еще могут достичь всего, что может машина Тьюринга, что делает их также завершенными:
- Нетипизированное лямбда-исчисление
- Игра жизни Конвея
- Шаблоны C++
- пролог
Из википедии:
Полнота Тьюринга, названная в честь Алана Тьюринга, важна тем, что любой вероятный проект для вычислительного устройства, которое до сих пор продвигалось, может быть воспроизведено универсальной машиной Тьюринга - наблюдение, которое стало известно как тезис Черча-Тьюринга. Таким образом, машина, которая может действовать как универсальная машина Тьюринга, в принципе может выполнять любые вычисления, на которые способен любой другой программируемый компьютер. Однако это не имеет никакого отношения к усилиям, необходимым для написания программы для машины, времени, которое может потребоваться машине для выполнения вычислений, или любым возможностям, которыми может обладать машина, которые не связаны с вычислениями.
В то время как по-настоящему полные по Тьюрингу машины, скорее всего, физически невозможны, поскольку для них требуется неограниченное хранилище, полнота по Тьюрингу часто слабо приписывается физическим машинам или языкам программирования, которые были бы универсальными, если бы у них было неограниченное хранилище. В этом смысле все современные компьютеры полны по Тьюрингу.
Я не знаю, как вы можете быть более нетехническим, чем это, за исключением того, что вы говорите, что "полное выполнение" означает "возможность ответить на вычислимую задачу при наличии достаточно времени и пространства" ".
По сути, полнота по Тьюрингу - это одно краткое требование, неограниченная рекурсия.
Даже не ограничен памятью.
Я думал об этом самостоятельно, но вот некоторые обсуждения этого утверждения. Мое определение LSP предоставляет больше контекста.
Другие ответы здесь не определяют напрямую фундаментальную сущность полноты по Тьюрингу.
Turing Complete означает, что он по крайней мере такой же мощный, как машина Тьюринга. Это означает, что все, что может быть вычислено машиной Тьюринга, может быть вычислено системой Turing Complete.
Никто еще не нашел систему, более мощную, чем Машина Тьюринга. Таким образом, в настоящее время говорить, что система является полной по Тьюрингу, - это то же самое, что говорить, что система является такой же мощной, как любая известная вычислительная система (см. Тезис Черча-Тьюринга).
Проще говоря, система, полная по Тьюрингу, может решить любую возможную вычислительную задачу.
Одним из ключевых требований является неограниченный размер блокнота, и его можно перемотать для доступа к предыдущим записям в блокнот.
Таким образом, на практике ни одна система не является полной по Тьюрингу.
Скорее, некоторые системы приближают полноту по Тьюрингу, моделируя неограниченную память и выполняя любые возможные вычисления, которые могут поместиться в памяти системы.
Супер-краткое изложение того, что профессор Бразилфорд объясняет в этом видео .
Полный Тьюринга делать все, что может сделать машина Тьюринга.
Он имеет условное ветвление (например, «оператор if»). Также подразумевается «перейти к» и, таким образом, разрешить цикл.
Он имеет произвольный объем памяти (например, достаточно длинную ленту), который требуется программе.
Что я понимаю простыми словами:
Завершение по Тьюрингу: язык / программа программирования, которая может выполнять вычисления, является завершением по Тьюрингу.
Например:
Можете ли вы добавить два числа, используя просто HTML. (Ответ - "Нет", для добавления необходимо использовать javascript.) Следовательно, HTML не является завершением по Тьюрингу.
Такие языки, как Java, C++, Python, Javascript, Solidity для Ethereum и т. Д., Являются Turing Complete, потому что вы можете выполнять вычисления, например, добавляя два числа, используя эти языки.
Надеюсь это поможет.
Я думаю, что важность концепции "полный Тьюринг" заключается в способности идентифицировать вычислительную машину (не обязательно механический / электрический "компьютер"), в которой ее процессы можно деконструировать в "простые" инструкции, состоящие из более простых и простых инструкции о том, что универсальная машина может интерпретировать, а затем выполнить.
Я очень рекомендую Аннотированную Тьюринг
@ Марк, я думаю, что вы объясняете, это сочетание описания универсальной машины Тьюринга и полной Тьюринга.
Что-то, что является Turing Complete, в практическом смысле было бы машиной / процессом / вычислением, которое можно записать и представить в виде программы, которая будет выполняться универсальной машиной (настольным компьютером). Хотя это не учитывает время или хранение, как уже упоминалось другими.
Как сказал Вэйлон Флинн:
Turing Complete означает, что он по крайней мере такой же мощный, как машина Тьюринга.
Я считаю, что это неверно, система завершена по Тьюрингу, если она точно такая же мощная, как машина Тьюринга, то есть все вычисления, выполняемые машиной, могут выполняться системой, но также все вычисления, выполняемые системой, могут выполняться машиной Тьюринга.,
Машина Тьюринга требует, чтобы любая программа могла выполнять проверку условий. Это фундаментально.
Рассмотрим пианино игрока. Пианино может играть очень сложное музыкальное произведение, но в музыке никогда не бывает условной логики. Это полный Тьюринг.
Условная логика - это одновременно сила и опасность машины, являющейся полной по Тьюрингу.
Пианино каждый раз гарантированно останавливается. На ТМ такой гарантии нет. Это называется "проблема остановки".
В практических языковых терминах, знакомых большинству программистов, обычный способ определения полноты по Тьюрингу заключается в том, что язык разрешает или разрешает моделирование вложенных неограниченных операторов while (в отличие от операторов в стиле Pascal с фиксированными верхними границами).
Мы называем язык полным по Тьюрингу тогда и только тогда, когда (1) он разрешим с помощью машины Тьюринга, но (2) не может быть разрешен с помощью чего-либо менее мощного, чем машина Тьюринга. Например, язык палиндромов над алфавитом {a, b} разрешим машинами Тьюринга, но также и автоматами выталкивания вниз; Таким образом, этот язык не является полным по Тьюрингу. По-настоящему полные по Тьюрингу языки, требующие полной вычислительной мощности машин Тьюринга, довольно редки. Возможно, это язык строк xyz, где x — число, y — машина Тьюринга, а z — начальная конфигурация ленты, а y останавливается на z менее чем за x! шаги - возможно, это подходит (хотя это нужно было бы показать!)
Распространенное неточное использование путает полноту по Тьюрингу с эквивалентностью по Тьюрингу. Эквивалентность по Тьюрингу относится к свойству вычислительной системы, которая может моделировать машины Тьюринга и которые могут быть смоделированы ими. Мы могли бы сказать, что Java — это язык программирования, эквивалентный Тьюрингу, например, потому что вы можете написать симулятор машины Тьюринга на Java и потому что вы можете определить машину Тьюринга, которая имитирует выполнение программ Java. Согласно тезису Черча-Тьюринга, машины Тьюринга могут выполнять любые эффективные вычисления, поэтому эквивалентность по Тьюрингу означает, что система обладает максимально возможными возможностями (если тезис Черча-Тьюринга верен!)
Эквивалентность по Тьюрингу - гораздо более распространенная проблема, чем истинная полнота по Тьюрингу; это, а также тот факт, что «полный» короче, чем «эквивалентный», может объяснить, почему «полный по Тьюрингу» так часто неправильно используется для обозначения эквивалентного по Тьюрингу, но я отвлекся.
Он завершен, если он может тестировать и ветвиться (имеет 'если')
Может ли реляционная база данных ввести широту и долготу мест и дорог и вычислить кратчайший путь между ними - нет. Это одна из проблем, которая показывает, что SQL не завершен по Тьюрингу.
Но C++ может сделать это, и может решить любую проблему. Так и есть.