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

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

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

10.08.2008 18:41:02
Некоторые очень хорошие ссылки на этот вопрос .
Lazer 27.05.2010 15:56:22
14 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

316
10.08.2008 20:10:48
Для дальнейшего чтения, см. Аннотированная Тьюринг. Очень доступный amazon.com/Annotated-Turing-Through-Historic-Computability/dp/…
i_am_jorf 18.05.2009 17:19:36
«часто не на практике» неверно. На практике ни одна система никогда не будет полной по Тьюрингу, потому что ни в одной реализуемой системе нет бесконечной ленты. На самом деле мы имеем в виду, что некоторые системы обладают способностью аппроксимировать полноту по Тьюрингу вплоть до пределов доступной памяти.
Shelby Moore III 8.08.2014 22:40:31
Но Vi - единственный вычислительный движок, когда-либо необходимый в мире ... ;-)
Joe Edgar 15.08.2014 05:07:09
Emacs - тоже токарный станок? XD
alem0lars 16.02.2015 18:57:40
Кто-то недавно показал, что PowerPoint тоже Turing Complete.
Tagc 30.04.2017 12:57:00

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

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

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

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

86
10.08.2008 18:59:06
В этом контексте, что такое «вычислительное устройство»?
dopatraman 13.11.2014 16:43:11
Как и в большинстве статей Википедии, хотя эта цитата технически верна, она не представляет никакой ценности для человека, который не знает об этом предмете и пытается его понять.
Lacho Tomov 25.09.2017 15:19:28

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

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

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

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

2
10.11.2012 10:17:08

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

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

11
28.04.2015 11:20:35
Обратите внимание, что все это игнорирует время стены. Это просто говорит, что это может быть сделано.
Thorbjørn Ravn Andersen 27.09.2010 15:53:41
@ ThorbjørnRavnAndersen на самом деле, он вообще игнорирует физическую вычислимость. Мало того, что это займет больше времени, чем возраст вселенной, но также может использовать больше памяти, чем может быть создано со всеми фермионами и бозонами во вселенной.
Waylon Flinn 9.05.2016 17:25:20
Не исключено, что количество всевозможных бозонов и фермионов во вселенной не ограничено. Мы не знаем, и, вероятно, никогда не узнаем, это размер. Каждый раз, когда вы читаете о числе X во «вселенной», люди на самом деле говорят о наблюдаемой вселенной. Хотя интересно, это не фактический физический предел.
Stijn de Witt 23.06.2017 21:59:54

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

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

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

-1
23.05.2017 11:47:28
Я думаю, вы предполагаете, что тезис Черча-Тьюринга верен, чтобы прийти к такому выводу. Это еще предстоит доказать. Свойство, которое вы описываете, называется «Эквивалент Тьюринга».
Waylon Flinn 8.12.2009 13:41:38
@WaylonFlinn Нет, он прав. «Полнота» означает как то, что она, по крайней мере, так же сильна, как и вещь, но также не сильна. Сравните с «NP-Complete».
Devin Jeanpierre 23.01.2012 23:19:39
@DevinJeanpierre Я не хочу начинать пламенную войну здесь, но я почти уверен, что вычислительный класс, который вы описываете, называется «Эквивалент Тьюринга». Turing Complete имеет отношение, подобное NP-Complete. NP-Complete равно NP тогда и только тогда, когда P = NP. Точно так же Тьюринг-Полл равен Эквиваленту Тьюринга тогда и только тогда, когда тезис Черча-Тьюринга верен.
Waylon Flinn 27.01.2012 15:24:13
@ Waylon Source? Ничто из того, что я читаю, не согласуется с этим (например, en.wikipedia.org/wiki/Turing_completeness )
Devin Jeanpierre 29.01.2012 16:09:54
@DevinJeanpierre Это говорит об этом прямо в статье в Википедии, на которую вы ссылаетесь. Цитируя раздел «Формальные определения»: «Вычислительная система, которая может вычислять каждую вычислимую по Тьюрингу функцию, называется полной по Тьюрингу», «Полная по Тьюрингу система называется эквивалентной по Тьюрингу, если каждая функция, которую она может вычислить, также вычислима по Тьюрингу»
Waylon Flinn 31.01.2012 14:46:04

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

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

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

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

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

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

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

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

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

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

  • Нетипизированное лямбда-исчисление
  • Игра жизни Конвея
  • Шаблоны C ++
  • пролог
74
23.12.2017 21:33:03
SQL наиболее определенно завершен. Он имеет возможности сценариев, которые позволяют любые вычисления.
nzifnab 1.05.2011 00:41:15
Нет, вы путаете SQL с такими расширениями, как T-SQL / PL-SQL. ANSI SQL не является полным по Тьюрингу. Но TSQL / PLSQL - есть.
Agnius Vasiliauskas 3.07.2011 17:58:06
По-видимому, SQL завершен по
Newtang 29.07.2012 23:59:54
В соответствии с полнотой Тьюринга - система Тьюринга завершена, если ее можно использовать для моделирования любой машины Тьюринга с одной лентой. Но в приведенном выше примере, как я понял, разработчики разработали конкретное cyclic tag systemи нет universal cyclic tag system. Следовательно, статья не доказывает полноту SQL-тестирования. (Или я что-то не так понял)
Agnius Vasiliauskas 2.10.2012 13:06:25
Не существует реализуемой реализации языка, полного по Тьюрингу, потому что нет бесконечных лент. На самом деле мы имеем в виду, что некоторые языки обладают способностью аппроксимировать полноту по Тьюрингу вплоть до пределов доступной памяти хост-машины.
Shelby Moore III 8.08.2014 22:34:36

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

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

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

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

17
23.05.2017 12:02:46
Конечные автоматы могут иметь неограниченную рекурсию. Дело в точке: a*.
user824425 4.06.2014 16:10:27
@Rhymoid FSM имеют ограниченную память ( конечное число состояний), но неограниченная рекурсия без хвостовой оптимизации должна иметь неограниченную память. Я не ограничивал свое определение подмножеством неограниченной рекурсии только с помощью хвостовой оптимизации. Пожалуйста, удалите ваш downvote.
Shelby Moore III 23.07.2014 11:13:22
Вы сохранили определение неограниченной рекурсии. Вы имеете в виду «рекурсия» в смысле «примитивная рекурсия» и «неограниченная», делая ее «частичной» (или «общей», или «му-»)? Тогда вы можете быть правы. Но ваша нынешняя формулировка слишком близка к заявлениям, раскритикованным в «Народных теоремах» Дэвида Харела. Важно быть строгим в математике, и, оставляя точные определения, вы игнорируете это. Кстати: автоматы могут быть обобщены для моделирования взаимодействия; что отличает их от TM, так это то, что среда последнего также моделируется (как лента).
user824425 23.07.2014 11:26:48
@ Rhymoid перечисление является антитезой точности, например, перечислите максимальную точность долей дюйма. Неограниченная рекурсия означает любую возможную форму рекурсии, которая невозможна без бесконечной ленты. Полностью обобщенная рекурсия (не только общая внутри модели) всегда завершается по Тьюрингу. Я утверждаю эквивалентность между обобщенной рекурсией и способностью выполнять любые возможные вычисления. Это важный эквивалент, чтобы отметить.
Shelby Moore III 8.08.2014 22:22:00
«Неограниченная рекурсия означает любую возможную форму рекурсии». Это ваше чтение. Для большинства пользователей SO «неограниченная рекурсия» означает while (p) { /* ... */ }. «Я констатирую эквивалентность между обобщенной рекурсией и способностью выполнять любые возможные вычисления». Тезис Черча - это совсем другой вопрос, и его действительно нужно обсуждать отдельно.
user824425 8.08.2014 23:20:57

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

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

-8
15.12.2012 18:33:53
Возможность вычисления кратчайшего пути между точками не является полным определением Тьюринга. Это гораздо больше, чем просто один пример.
Eva 20.02.2013 23:48:20
Я просто выложу
Matthew Whited 23.10.2015 10:46:49

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

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

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

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

9
8.08.2014 22:50:53

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

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

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

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

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

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

184
23.06.2019 17:18:11
Мысль о том, что для такого типа машин даже есть термин, имеет гораздо больше смысла, когда я помню, как Тьюринг и другие ранние компьютерные ученые создавали конкретную машину каждый раз, когда хотели решить конкретную проблему. Мы привыкли к одной машине, которую можно перепрограммировать навсегда. Спасибо за контекст, Раджа.
Jacob Ford 13.08.2017 14:32:12
Как JavaScript может быть завершен по Тьюрингу? Не хватает файловой системы, правильного многопоточного API. Он имеет множество ограничений, в основном из-за своей изолированной среды безопасности браузера. Вряд ли это можно назвать «языком программирования». Посмотрите, сколько существует вариантов абстракции сценариев (реагируйте, машинопись… вы называете это), и все это для компенсации того, чего нет у JS. (asm.js должен быть упомянут здесь). Java, Python или C ++ являются настоящими примерами Turing Complete. Но JS? Я так не думаю.
Michael IV 19.12.2017 22:30:21
@MichaelIV У гастролирующей машины также не было файловой системы / потоков. JS полностью гастролирует.
Bax 21.01.2018 05:34:38
@MichaelIV Чтобы добавить к ответу Бакса, можно подумать, что современный компьютер состоит из нескольких машин Тьюринга, которые работают вместе, чтобы учесть все те приятные вещи, которые вы упомянули. Например, процессор создает «ленту» для чтения графическим процессором, чтобы он мог записывать «ленту» для монитора, чтобы монитор мог записывать «ленту» пользователю. Аналогичным образом, процессор может производить «ленту» для жестких дисков, сетевых карт, звуковых карт и т. Д.
user3003999 2.10.2018 14:33:40

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

-2
26.10.2016 20:12:17
Одного неограниченная цикла в то время как достаточно , чтобы имитировать машину Тьюринга.
masterxilo 17.04.2017 22:11:31

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

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

Например :

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

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

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

2
28.12.2018 15:39:42

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

0
15.01.2020 17:10:05
Для такого старого вопроса стоило бы проверить, не сделали ли другие уже такие же или более существенные вклады
alan ocallaghan 15.01.2020 17:16:04
Не уверен насчет правильности ответа. Но это действительно простое объяснение, которого я никогда раньше не видел. Забавно: давным-давно (после того, как я написал свой первый фрагмент кода), я также использовал то же объяснение, чтобы определить простейший возможный процессор.
Victor Yarema 15.01.2020 19:32:05
Это отличная первая попытка получить четкое, точное и точное определение. Однако ветвь должна разрешать зацикливание, и разве машина не должна разрешать вызовы подпрограмм (т. Е. Рекурсия)? Существует ли сплющенная программа вложенных циклов для каждой программы с рекурсией?
user3673 29.02.2020 15:41:15

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

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

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

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

0
18.03.2020 20:18:20