Что такое полный Тьюринга?
Что означает выражение «полный Тьюринга»?
Можете ли вы дать простое объяснение, не вдаваясь в слишком много теоретических деталей?
Ответы 15
От википедия:
Turing completeness, named after Alan Turing, is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine — an observation that has become known as the Church-Turing thesis. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other programmable computer is capable of. However, this has nothing to do with the effort required to write a program for the machine, the time it may take for the machine to perform the calculation, or any abilities the machine may possess that are unrelated to computation.
While truly Turing-complete machines are very likely physically impossible, as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage. All modern computers are Turing-complete in this sense.
Я не знаю, как вы можете быть более нетехническим, чем это, кроме как сказать «полная по Тьюрингу означает« способность ответить на вычислимую проблему при наличии достаточного времени и пространства »».
В этом контексте что такое «вычислительное устройство»?
Как и в большинстве статей в Википедии, хотя эта цитата технически верна, она не представляет ценности для человека, который не знает предмета и пытается его понять. Умение правильно объяснять вещи - это отдельная наука :)
Вот самое краткое объяснение:
Полная система Тьюринга означает систему, в которой можно написать программу, которая найдет ответ (хотя и без каких-либо гарантий относительно времени выполнения или памяти).
Итак, если кто-то говорит: «Моя новая вещь - Turing Complete», это означает в принципе (хотя часто и не на практике) ее можно использовать для решения любой вычислительной задачи.
Иногда это шутка ... парень написал симулятор машины Тьюринга на vi, поэтому можно сказать, что vi - единственный вычислительный движок, когда-либо необходимый в мире.
Для дальнейшего чтения см. Аннотированный Тьюринг. Очень доступный. amazon.com/Annotated-Turing-Through-Historic-Computability/d p /…
«часто не на практике» неверно. На практике ни одна система не бывает полной по Тьюрингу, потому что ни одна реализуемая система не имеет бесконечной ленты. На самом деле мы имеем в виду, что некоторые системы обладают способностью аппроксимировать полноту по Тьюрингу до пределов доступной им памяти.
Но Vi - единственный вычислительный движок, который когда-либо требовался в мире ... ;-)
Emacs тоже токарный станок? XD
Кто-то недавно показал, что PowerPoint тоже завершен по Тьюрингу.
Разрешима ли «любая вычислительная проблема», если ваша программа может правильно +, -, × и ÷? Или нужно больше? Знаем ли мы, что требуется для решения «любой вычислительной задачи», или это немного спорная загадка?
@JacobFord и бесконечное количество случайно доступного рабочего места, а также возможность принимать решения и зацикливаться
Когда кто-то заявляет, что что-то завершено по Тьюрингу, я думаю, стоит указать на Машина Тьюринга была создана в Игре Жизни. (1 цикл занимает 11040 поколений)
Для PowerPoint и некоторых других см. beza1e1.tuxen.de/articles/accidentally_turing_complete.html
Какие вещи разрешимы машиной Тьюринга и неразрешимы машиной, которая в остальном эквивалентна Тьюрингу, за исключением наличия конечной, а не неограниченной памяти?
Я понимаю, что вы сейчас говорите: для каждого вычисления C, которое разрешимо на машине Тьюринга M, которое разрешимо на другой машине N, эта другая машина N является полной по Тьюрингу для этого вычисления C. Таким образом, язык программирования "C" и соответствующий реальный мир машины с конечной памятью являются полными по Тьюрингу для каждого разрешимого вычисления, которое также разрешимо с помощью машины Тьюринга.
Я думаю, что важность концепции «Полный Тьюринга» заключается в способности идентифицировать вычислительную машину (не обязательно механический / электрический «компьютер»), процессы которой можно деконструировать в «простые» инструкции, состоящие из более простых и простых. инструкции, которые универсальная машина может интерпретировать и затем выполнять.
Я очень рекомендую The Annotated Turing
@Mark, я думаю, что вы объясняете смесь между описанием Универсальной машины Тьюринга и Полного Тьюринга.
Что-то, что является Turing Complete, в практическом смысле, будет машиной / процессом / вычислением, которое можно написать и представить в виде программы, которая будет выполняться универсальной машиной (настольным компьютером). Хотя это не учитывает время или хранение, как упоминалось другими.
Полный Тьюринга означает, что он, по крайней мере, столь же мощный, как Машина Тьюринга. Это означает, что все, что может быть вычислено машиной Тьюринга, может быть вычислено полной системой Тьюринга.
Еще никто не нашел системы более мощной, чем машина Тьюринга. Итак, на данный момент сказать, что система является полной по Тьюрингу, - это то же самое, что сказать, что система столь же мощна, как и любая известная вычислительная система (см. Тезис Черча-Тьюринга).
Обратите внимание, что все это не учитывает время на стене. Он просто говорит: «Это можно сделать».
@ ThorbjørnRavnAndersen вообще-то игнорирует физическую вычислимость. Это может не только занять больше времени, чем возраст Вселенной, но и использовать больше памяти, чем может быть создано с помощью всех фермионов и бозонов во Вселенной.
Вполне возможно, что нет предела количеству бозонов и фермионов во Вселенной. Мы не знаем и, вероятно, никогда не узнаем его размера. Каждый раз, когда вы читаете о числе X во «вселенной», люди на самом деле говорят о вселенной наблюдаемый. Хотя это интересно, это не физический предел.
Как Вэйлон Флинн сказал:
Turing Complete means that it is at least as powerful as a Turing Machine.
Я считаю, что это неверно, система является полной по Тьюрингу, если она такая же мощная, как машина Тьюринга, т.е. каждое вычисление, выполняемое машиной, может выполняться системой, но также каждое вычисление, выполняемое системой, может выполняться машиной Тьюринга. .
Я думаю, вы предполагаете, что тезис Черча-Тьюринга верен, чтобы прийти к такому выводу. Это еще предстоит доказать. Свойство, которое вы описываете, называется «эквивалентом Тьюринга».
@WaylonFlinn Нет, он прав. «Полнота» означает и то, что он, по крайней мере, так же силен, как вещь, но не сильнее. Сравните с «НП-Комплект».
@DevinJeanpierre Я не хочу начинать здесь войну пламени, но я почти уверен, что описываемый вами вычислительный класс называется «Эквивалент Тьюринга». Однако Turing Complete имеет аналогичное отношение к NP-Complete. NP-Complete равно NP тогда и только тогда, когда P = NP. Точно так же Полное Тьюринга равно Тьюринговому Эквиваленту тогда и только тогда, когда тезис Черча-Тьюринга верен.
@ Источник Уэйлона? Все, что я прочитал, не согласуется с этим (например, en.wikipedia.org/wiki/Turing_completeness)
@DevinJeanpierre Об этом говорится прямо в статье в Википедии, на которую вы ссылаетесь. Цитата из раздела «Формальные определения»: «Вычислительная система, которая может вычислить каждую функцию, вычисляемую по Тьюрингу, называется полной по Тьюрингу», «Полная по Тьюрингу система называется эквивалентом по Тьюрингу, если каждая функция, которую она может вычислить, также вычислима по Тьюрингу»
Неформальное определение
Полный язык Тьюринга - это язык, который может выполнять любые вычисления. Тезис Черча-Тьюринга утверждает, что любое выполнимое вычисление может быть выполнено машиной Тьюринга. Машина Тьюринга - это машина с бесконечной оперативной памятью и конечной «программой», которая диктует, когда она должна читать, писать и перемещаться по этой памяти, когда она должна завершиться с определенным результатом и что делать дальше. Входные данные машины Тьюринга перед запуском помещаются в ее память.
Вещи, которые могут сделать язык НЕ полным по Тьюрингу
Машина Тьюринга может принимать решения на основе того, что видит в памяти - «язык», который поддерживает только +, -, * и / для целых чисел, не является полным по Тьюрингу, потому что он не может сделать выбор на основе своего ввода, а машина Тьюринга может.
Машина Тьюринга может работать вечно - если бы мы взяли Java, Javascript или Python и удалили возможность выполнять любой цикл, GOTO или вызов функции, это не было бы полным по Тьюрингу, потому что он не может выполнять произвольное вычисление, которое никогда не завершается. Coq - это средство доказательства теорем, которое не может выражать программы, которые не завершаются, поэтому он не завершен по Тьюрингу.
Машина Тьюринга может использовать бесконечную память - язык, который был в точности похож на Java, но прекращал свою работу, когда он использовал более 4 гигабайт памяти, не был бы полным по Тьюрингу, потому что машина Тьюринга может использовать бесконечную память. Вот почему мы не можем на самом деле строить машина Тьюринга, но Java по-прежнему является полным языком Тьюринга, потому что Java язык не имеет ограничений, препятствующих использованию бесконечной памяти. Это одна из причин, по которой регулярные выражения не полны по Тьюрингу.
Машина Тьюринга имеет оперативную память - язык, который позволяет вам работать с памятью только через операции push и pop в стеке, не будет полным по Тьюрингу. Если у меня есть `` язык '', который читает строку однажды и может использовать память только путем нажатия и извлечения из стека, он может сказать мне, имеет ли каждый ( в строке свой собственный ) позже, нажав, когда он видит (, и появляется, когда видит ). Однако он не может сказать мне, имеет ли каждый ( свой собственный ) позже и каждый [ будет иметь свой собственный ] позже (обратите внимание, что ([)] соответствует этим критериям, а ([]] нет). Машина Тьюринга может использовать свою оперативную память для отслеживания () и [] по отдельности, но этот язык с одним стеком не может.
Машина Тьюринга может моделировать любую другую машину Тьюринга - машина Тьюринга, когда ей дана соответствующая «программа», может взять «программу» другой машины Тьюринга и смоделировать ее на произвольном входе. Если бы у вас был язык, на котором запрещено реализовывать интерпретатор Python, он не был бы полным по Тьюрингу.
Примеры полных языков по Тьюрингу
Если ваш язык имеет бесконечную оперативную память, условное выполнение и некоторую форму повторного выполнения, вероятно, он завершен по Тьюрингу. Существуют более экзотические системы, которые все еще могут достичь всего, что может машина Тьюринга, что также делает их полными по Тьюрингу:
- Нетипизированное лямбда-исчисление
- Игра жизни Конвея
- Шаблоны C++
- Пролог
SQL определенно является полным по Тьюрингу. Он имеет возможности создания сценариев, которые позволяют выполнять любые вычисления.
Нет, вы путаете SQL с такими расширениями, как T-SQL / PL-SQL. ANSI SQL не является полным по Тьюрингу. Но TSQL / PLSQL - есть.
Очевидно, SQL завершен по Тьюрингу: stackoverflow.com/questions/900055/…
Согласно полнота по Тьюрингу - система является полной по Тьюрингу, если ее можно использовать для моделирования любой однопленочной машины Тьюринга. Но в приведенном выше примере, как я понял, разработчики создали конкретный cyclic tag system, а не universal cyclic tag system. Следовательно, статья не доказывает полноту тьюринга SQL. (Или я что-то неправильно понял)
Не существует реализуемой реализации полного по Тьюрингу языка, потому что нет бесконечных лент. На самом деле мы имеем в виду, что некоторые языки обладают способностью приближать полноту по Тьюрингу к пределам доступной памяти хост-машины.
«Игра жизни» Конвея тоже завершена по Тьюрингу. en.wikipedia.org/wiki/Conway's_Game_of_Life
@Ejaz, Нет, это тип представления данных. см. stackoverflow.com/questions/15488658/… для получения дополнительной информации
Что вы имеете в виду, говоря «Регулярные выражения не являются полными по Тьюрингу»? RE выполняет вычисления, чтобы получить определенный результат, как и любая программа. Не могли бы вы объяснить?
По сути, полнота по Тьюрингу - это одно краткое требование - неограниченная рекурсия.
Даже не ограниченный памятью.
Я думал об этом самостоятельно, но вот некоторое обсуждение утверждения. Мое определение LSP предоставляет больше контекста.
Другие ответы здесь не определяют напрямую фундаментальную сущность полноты по Тьюрингу.
Автоматам с конечным числом состояний разрешена неограниченная рекурсия. Показательный пример: a*.
@Rhymoid FSMs ограниченная память - конечное количество состояний), но неограниченная рекурсия без хвостовой оптимизации должна иметь неограниченную память. Я не ограничивал свое определение подмножеством неограниченной рекурсии только с оптимизацией хвоста. Пожалуйста, удалите свой голос против.
вы сохранили определение неограниченной рекурсии в тумане. Вы имеете в виду «рекурсию» в смысле «примитивной рекурсии» и «неограниченный», делая ее «частичной» (или «общей», или «мю-»)? Тогда ты, наверное, прав. Но ваша нынешняя формулировка слишком близка к утверждениям, критикующим в «О народных теоремах» Дэвида Харела. В математике важно быть строгим, и, опуская точные определения, вы игнорируете это. Кстати: конечные автоматы можно обобщить на модели взаимодействия; что отличает их от TM, так это то, что среда последних также моделируется (как лента).
@Rhymoid enumeration - это полная противоположность точности, например перечислить максимальную точность до долей дюйма. Неограниченная рекурсия означает все возможные формы рекурсии, что невозможно без бесконечной ленты. Полностью обобщенная рекурсия (а не только общая в рамках модели) всегда является полной по Тьюрингу. Я заявляю об эквивалентности обобщенной рекурсии и способности выполнять любые возможные вычисления. Следует отметить важную эквивалентность.
«Неограниченная рекурсия означает все возможные формы рекурсии» Это чтение ваш. Для большинства пользователей SO «неограниченная рекурсия» означает while (p) { /* ... */ }. «Я заявляю об эквивалентности обобщенной рекурсии и способности выполнять любые возможные вычисления». Тезис Черча - это совсем другой вопрос, и о В самом деле стоит говорить отдельно.
@Rhymoid unhalting loops без побочных эффектов, ничего не вычисляет. (С побочными эффектами вычисления полностью обобщены в рамках модели.) Очевидно, я не мог иметь в виду, что данная полнота по Тьюрингу связана с общностью вычислений. Сказать больше с меньшим количеством слов - это черта высокого IQ (обратите внимание, я не утверждал, что это лучший вариант при общении со всеми аудиториями). Здесь уместно отнести эквивалентность Черча к более сжатому пониманию полноты по Тьюрингу. Спасибо за обсуждение и указатели. Надеюсь, это прояснится.
В вашем ответе было сказано: «По сути, полнота по Тьюрингу - это одно краткое требование - неограниченная рекурсия. Даже не ограниченный памятью.», я предположил, что это означает «даже не ограниченный ограниченной памятью». Хотя в комментариях вы говорите: «Неограниченная рекурсия означает все возможные формы рекурсии, что невозможно без бесконечной ленты.» Я понимаю, что для машины Тьюринга лента = память отсюда следует, что ничто не является полным по Тьюрингу, поскольку ничто не имеет бесконечной памяти. Что я здесь упускаю или неправильно понимаю? Не могли бы вы, любезно, уточнить?
Думаю, я нашел ответ на свой вопрос в Эта статья, который гласит: «... неограниченная рекурсия - то есть возможность вызывать небольшие программы (также известные как функции), которые могут вызывать себя до бесконечности.», как я понял, это означает, что неограниченная рекурсия (как следует из его названия =) это способность к рекурсии неограниченное, но конечное (что означает, что фактическое количество шагов конечно , но вы всегда можете сделать шаги п + 1) количество раз.
Может ли реляционная база данных вводить широту и долготу мест и дорог и вычислять кратчайший путь между ними - нет. Это одна из проблем, которая показывает, что SQL не является полным по Тьюрингу.
Но C++ может это сделать, и может решить любую проблему. Так оно и есть.
Возможность вычислить кратчайший путь между точками не является полным по Тьюрингу. Это гораздо больше, чем просто один пример.
Я просто положу сюда ... hansolav.net/blog/ImplementingDijkstrasAlgorithmUsingTSQL.as px
Проще говоря, полная по Тьюрингу система может решить любую возможную вычислительную проблему.
Одним из ключевых требований является неограниченный размер блокнота и возможность перемотки назад для доступа к предыдущим операциям записи в блокнот.
Таким образом, на практике ни одна система не является полной по Тьюрингу.
Некоторые системы скорее приближаются к полноте по Тьюрингу, моделируя неограниченную память и выполняя любые возможные вычисления, которые могут уместиться в памяти системы.
Вот самое простое объяснение
Алан Тьюринг создал машину, которая может взять программу, запустить ее и показать какой-то результат. Но тогда ему пришлось создавать разные машины для разных программ. Поэтому он создал «универсальную машину Тьюринга», которая может взять ЛЮБУЮ программу и запустить ее.
Языки программирования похожи на эти машины (хотя и виртуальные). Они берут программы и запускают их. Теперь язык программирования называется «завершенным по Тьюрингу», если он может запускать любую программу (независимо от языка), которую машина Тьюринга может запустить при наличии достаточного количества времени и памяти.
Например: Допустим, есть программа, которая складывает 10 чисел. Эту программу легко запустить на машине Тьюринга. Но теперь представьте, что по какой-то причине ваш язык программирования не может выполнять такое же дополнение. Это сделало бы его «неполным по Тьюрингу» (так сказать). С другой стороны, если он может запускать любую программу, которую может запустить универсальная машина Тьюринга, то он завершен.
Большинство современных языков программирования (например, Java, JavaScript, Perl и т. д.) Являются полными по Тьюрингу, потому что каждый из них реализует все функции, необходимые для запуска программ, таких как сложение, умножение, условие if-else, операторы возврата, способы сохранения / извлечения / стирания данные и так далее.
Обновление: вы можете узнать больше в моем сообщении в блоге: «JavaScript завершен по Тьюрингу» - объяснено
Идея о том, что для такого типа машин будет даже термин, имеет гораздо больше смысла, когда я вспоминаю, что Тьюринг и другие ранние компьютерные ученые создавали конкретную машину каждый раз, когда они хотели решить конкретную проблему. Мы привыкли к одной машине, которую можно вечно перепрограммировать. Спасибо за контекст, Раджа.
Как JavaScript может быть полным по Тьюрингу? Отсутствует файловая система, полноценный API многопоточности. Он имеет множество ограничений, в основном из-за того, что он использует изолированную программную среду безопасности браузера. Его вряд ли можно назвать «языком программирования». Посмотрите, сколько существует вариантов абстракции сценариев (реагируйте, машинописный текст ... вы называете это), и все это для компенсации того, чего нет в JS. (здесь следует упомянуть asm.js). Java, Python или C++ являются истинными примерами "Turing Complete". Но js? Я так не думаю.
@MichaelIV У туристической машины тоже не было файловой системы / потоков. JS полностью завершен.
@MichaelIV Чтобы добавить к ответу Бакса, можно сказать, что современный компьютер состоит из несколько машин Тьюринга, которые работают вместе, чтобы обеспечить все те приятные вещи, о которых вы упомянули. Например. ЦП создает «ленту» для чтения графическим процессором, чтобы он мог записывать «ленту» для монитора, чтобы монитор мог записывать «ленту» пользователю. Точно так же ЦП может производить «ленту» для жестких дисков, сетевых адаптеров, звуковых карт и т. д.
ссылка на сообщение в блоге не работает
JS является абсолютно полным по Тьюрингу, но полнота по Тьюрингу - это более низкая планка, чем вы можете себе представить. Это не значит, что он оптимален для любых вычислений. Например: языку не нужно иметь возможность умножать числа, чтобы быть полным по Тьюрингу, если он может складывать числа, зацикливаться и выполнять условные операторы. Это завершено по Тьюрингу, потому что вы можете написать функцию для умножения чисел с другими функциями.
В практических языковых терминах, знакомых большинству программистов, обычный способ определения полноты по Тьюрингу состоит в том, если язык позволяет или позволяет моделировать вложенные неограниченные операторы while (в отличие от операторов for в стиле Паскаля с фиксированными верхними границами).
Неограниченного цикла while Один достаточно для моделирования машины Тьюринга.
Что я понимаю простыми словами:
Тьюринг завершен: Язык программирования / программа, которая может выполнять вычисления, завершена по Тьюрингу.
Например :
Можете ли вы сложить два числа, используя Just HTML. (Ответ - 'Нет', для выполнения добавления необходимо использовать javascript.) Следовательно, HTML не является полным по Тьюрингу.
Такие языки, как Java, C++, Python, Javascript, Solidity для Ethereum и т. д., Являются полными по Тьюрингу, потому что вы можете выполнять вычисления, такие как сложение двух чисел, используя эти языки.
Надеюсь это поможет.
"может выполнять вычисления" явно недостаточно: используя ручной калькулятор, вы можете вычислять такие вещи, как 1 + 1 и cos (sin (exp (42))), но у вас нет циклов while (или даже циклов for) или неограниченная рекурсия (или даже просто возможность определять новые функции), поэтому она не может быть полной по Тьюрингу.
Он завершен, если он может тестировать и ветвиться (имеет 'если')
Для такого старого вопроса было бы целесообразно проверить, не внесли ли уже другие аналогичные или более существенные вклады.
Не уверен в правильности ответа. Но это действительно простое объяснение, которого я никогда раньше не видел. Забавно: давным-давно (после того, как я написал свой первый фрагмент кода) я также использовал то же объяснение для определения простейшего процессора.
Это отличная первая попытка четкого, краткого и точного рабочего определения. Однако ветвь должна разрешать зацикливание, и разве машина не должна также разрешать вызовы подпрограмм (например, рекурсию)? Есть ли сглаженная программа вложенных циклов для каждой программы с рекурсией?
Машина Тьюринга требует, чтобы любая программа может выполнять проверку условий. Это фундаментально.
Рассмотрим пианино игрока. Пианист может сыграть очень сложное музыкальное произведение, но в Музыка. Это нет Turing Complete.
Условная логика - это одновременно и сила, и опасность машины, которая является полной по Тьюрингу.
Пианино каждый раз гарантированно останавливается. На ТМ такой гарантии нет. Этот называется «проблема остановки».
Супер-краткое изложение того, что профессор Бразилфорд объясняет в этом видео.
Полный Тьюринга ≅ делать все, что может сделать машина Тьюринга.
Он имеет условное ветвление (т.е. «оператор if»). Также подразумевается «перейти к» и, таким образом, разрешить цикл.
У него есть произвольный объем памяти (например, достаточно длинная лента), которая нужна программе.
Несколько очень хороших ссылок на этот ТАК вопрос.