Что такое Тьюринг?

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

От wikipedia:

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

В простейших терминах система Turing-complete может решить любую возможную вычислительную проблему.

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

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

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

Ответ 8

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

Я очень рекомендую The Annotated Turing

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

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

Ответ 9

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

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

Например :

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

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

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

Ответ 10

Просто любопытно, что вы думаете о Blockchain, который масштабируется. Например, Биткойн С.В., что если вы можете хранить любую программу или операционную систему, а затем сеть в целом сможет выполнять любые функции и вычислять любое число? Потому что сетевое хранилище можно постоянно расширять, а также потому, что мы всегда можем написать или создать дополнительные программы, чтобы расширить возможности такого блокчейна. Та же идея, что ИИ мог писать свои собственные программы. Он живет в интернете с неограниченными ресурсами.

Ответ 11

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

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

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

Ответ 12

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

Ответ 13

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

Но С++ может это сделать и может делать какие-либо проблемы. Так оно и есть.