Что такое Завершение по Тьюрингу?

Question

Что означает выражение "Завершение по Тьюрингу"?

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

От википедия:

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

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Answer 8

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

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

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

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

Answer 9

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

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

Например :

1. Можете ли вы сложить два числа, используя только HTML.(Ответ - это 'НЕТ', вы должны использовать javascript для выполнения сложения.), следовательно, HTML не является полным по Тьюрингу.

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

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

Answer 10

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

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

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

Answer 11

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

Answer 12

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

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