Что делает язык Тьюринга полным?

79

Каков минимальный набор языковых функций / структур, которые делают его полным по Тьюрингу?

Любопытный кот
источник
21
Не лучше ли просто погуглить? ru.wikipedia.org/wiki/Turing_completeness
aml90
2
Привет, Любопытный Кот, добро пожаловать в Программисты! Звонки для списков здесь не по теме: я удалил эту часть из вашего вопроса. Тем не менее, этот квест чрезвычайно широк: есть ли конкретная проблема, над которой вы работаете, вы думаете о полноте по Тьюрингу?
3
@amalantony: просто как сноска .
Бобби
С точки зрения информатики, смотрите здесь .
Рафаэль

Ответы:

73

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

  • Iota и Jot - это функциональные языки с двумя и тремя символами соответственно, основанные на исчислении комбинаторов SK (I) .

  • OISC ( один компьютер с набором инструкций ) обозначает тип императивного вычисления, для которого требуется только одна инструкция из одного или нескольких аргументов, обычно «вычитание и ветвление, если оно меньше или равно нулю», или «обратное вычитание и пропуск, если заимствование». MMU x86 реализует прежнюю инструкцию и, таким образом, завершается по Тьюрингу.

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

  1. Форма условного повторения или условного перехода (например while, if+ goto)

  2. Способ чтения и записи некоторой формы хранения (например, переменные, лента)

Чтобы функциональный язык на основе лямбда-исчисления был TC, ему необходимо:

  1. Возможность абстрагировать функции над аргументами (например, лямбда-абстракция, цитата)

  2. Возможность применять функции к аргументам (например, сокращение)

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

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

Джон Перди
источник
Для императивных языков достаточно ли простых переменных? У меня сложилось впечатление, что потребуется какая-то коллекция (например, массивы или связанные списки).
luiscubal
1
@luiscubal вы должны иметь возможность указать произвольный объем данных. С помощью простых переменных вы можете представить объем данных, которые имеют сами переменные. Что делать, если вам нужно представить N + 1 различных частей данных. Можно утверждать, что с помощью трюков, подобных играм Фрактрана, вы можете делать это даже в простых переменных ... но это не совсем то, о чем вы просите.
Разве не требуется, чтобы язык поддерживал циклы ENDLESS ?
Сергей
Ре, «каждый полезный язык имеет способ взаимодействия с миром». У Алгола 60 не было определенного способа взаимодействия с миром. Все ваши операции ввода-вывода в программе Algol 60 выполнялись путем вызова библиотечных функций, и библиотечные функции могли быть совершенно разными в разных реализациях. Но я тем самым отказываюсь от любого обсуждения того, был ли Алгол 60 «полезным».
Соломон Медленный
15

С более практической точки зрения: если вы можете перевести все программы на языке, полном по Тьюрингу, на свой язык, то (насколько я знаю) ваш язык должен быть полным по Тьюрингу. Поэтому, если вы хотите проверить, является ли разработанный вами язык полным по Тьюрингу, вы можете просто написать Brainf *** для компилятора YourLanguage и доказать / продемонстрировать, что он может компилировать все легальные BF-программы.

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

Антон Голов
источник
11
Да, это определенно самый практичный способ приблизиться к этому. </sarcasm>
Роберт Харви
13
@RobertHarvey имеет смысл, но общая идея весьма жизненно важна. Доказано, что Brainfuck является полным и очень простым, как языки программирования. Для неэзотерических языков программирования реализация интерпретатора brainfuck может быть намного проще и быстрее, чем давать строгое доказательство из ниоткуда (я могу реализовать BF в нескольких строках Python, но я не уверен, с чего начать с формального доказательство того, что Python завершен); и десятки эзотерических языков, вдохновленных бредовым мозгом, известны своей полной завершенностью, потому что известно, как они соответствуют бреду.
7
@RobertHarvey: почему бы и нет? Конечно, кто-то, проектирующий свой собственный язык, сможет написать для него BF-компилятор (если это необходимо, и найти подходящий другой язык в противном случае).
Антон Голов
5
@delnan: Вы должны будете доказать, однако, что ваш BF-интерпретатор правильно реализует спецификацию BF, поэтому вы должны будете доказать, что ваш BF-интерпретатор, по сути, является BF-интерпретатором, а не интерпретатором для BF-подобного языка, который может быть или не быть полным по Тьюрингу.
Йорг Миттаг
2
@ DarekNędza, это просто естественное следствие того, как определяется полнота Тьюринга; любое расширение языка Turing Complete по-прежнему будет Turing Complete.
Антон Голов
8

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

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

  1. Способность читать и записывать «переменные» (или произвольные данные) : в значительной степени говорит само за себя.
  2. Способность имитировать перемещение головки чтения / записи : недостаточно просто иметь возможность извлекать и хранить переменные. Также должна быть возможность имитировать способность перемещать головку ленты, чтобы ссылаться на другие переменные. Это часто может быть смоделировано в языках программирования с использованием структур данных массива (или эквивалентных) или, в случае некоторых языков, таких как машинный код, возможностью ссылаться на другие переменные с помощью «указателей» (или эквивалентных).
  3. Способность моделировать конечный автомат : хотя машины Тьюринга не упоминаются часто, на самом деле они представляют собой разновидность конечных автоматов, часто используемых при разработке ИИ. Алан Тьюринг сказал, что целью штатов является симуляция "различных способов решения проблем".
  4. Состояние «остановки» : хотя часто упоминается, что набор правил должен иметь возможность повторяться, чтобы считаться завершенным по Тьюрингу, это не очень хороший критерий, поскольку формальное определение алгоритма состояния должно быть всегда в конечном итоге сделать вывод. Если они не могут завершить каким-либо образом, либо он не завершен по Тьюрингу, либо указанный алгоритм не является вычислимой функцией. Тьюринг завершенных систем, которые технически не могут завершить работу из-за того, как они работают (например, игровые приставки), обходят это ограничение, имея возможность «имитировать» состояние остановки некоторым способом. Не путать с «проблемой остановки», неразрешимой функцией, которая доказывает это

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

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

user3067516
источник
4

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

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

Сложность по времени, сложность пространства, легкий формат ввода / вывода и простота написания любой программы не включены в уравнение, поэтому такая машина теоретически может выполнять все вычисления, если вычисления не останавливаются из-за потери мощности или проглатывания Земли солнцем.

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

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

Сильвестер
источник
2
«Язык программирования завершается, если вы можете сделать какие-либо вычисления с ним». Это тезис Церкви-Тьюринга, а не то, что делает язык Тьюринга полным.
Рифмовидная
@Rhymoid То есть ты имеешь в виду, что ничто не может быть завершено, если ты не можешь сделать переводчика? То есть. Лямбда-исчисление не является полным по Тьюрингу, даже если оно равнозначно?
Сильвестр
1
Я все еще ищу авторитетное определение терминов, эквивалентных по Тьюрингу, и полного по Тьюрингу (и мощных по Тьюрингу). Я уже видел слишком много случаев, от людей на досках объявлений до исследователей в своих собственных чертовых документах, которые по-разному интерпретируют эти термины.
Рифмоид
В любом случае, я интерпретирую «полный Тьюринг» как симуляцию, эквивалентную универсальной машине Тьюринга (UTM; которая, в свою очередь, способна моделировать любую машину Тьюринга - следовательно, «универсальную»). В работе Тьюринга от 1936 года, где он представил свои машины, он определил понятие UTM и дал набросок доказательства того, что UTM являются симуляцией, эквивалентной лямбда-исчислению Черча. Тем самым он доказал, что они обладают одинаковыми вычислительными возможностями. Тезис Черча-Тьюринга, проще говоря, утверждает, что «это все вычислительные мощности, которые вы когда-либо получите».
Rhymoid
У этого есть два формальных определения для страницы полноты Тьюринга Википедии . Один требует ввода / вывода, другой нет. Тот, который не говорит, что машина завершается по Тьюрингу, если она может вычислить каждую вычислимую по Тьюрингу функцию. Это возвращает лямбда-исчисление к завершению по Тьюрингу, так как вы можете легко создать эквивалентную программу в лямбда-исчислении, которая вычисляет так же, как любые программы машин Тьюринга.
Сильвестр
4

Вы не можете сказать, будет ли это петля бесконечно или остановится.

-------------

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

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

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

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

Например, предположим, что вы хотите доказать, что Snakes & Ladders завершена по Тьюрингу, учитывая доску с бесконечно повторяющимся узором сетки (с другой версией сверху и слева). Зная, что машина Мински с 2 счетчиками завершена по Тьюрингу (которая имеет 2 неограниченных счетчика и 1 состояние из конечного числа), вы можете построить эквивалентную доску, где позиции X и Y на сетке - это текущее значение 2 счетчиков. и текущий путь является текущим состоянием. Взрыв! Вы только что доказали, что Змеи и Лестницы завершены.

Хьюберт Ламонтань
источник
1
Я не покупаю этот аргумент. Тот факт, что проблема остановки неразрешима для машин Тьюринга, не означает, что каждая нотация, позволяющая указать программу, для которой проблема остановки неразрешима, является завершенной по Тьюрингу. Очевидно, верно только обратное: если запись Тьюринга завершена, то, конечно, можно писать программы, для которых проблема остановки неразрешима.
5gon12eder
Это необходимое условие. Если вы можете решить для каждой программы, останавливается ли она, язык не завершен по Тьюрингу.
gnasher729
4

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

Например, функция Аккермана не может быть вычислена на языке без этих функций. С другой стороны, можно написать много очень сложного и очень полезного программного обеспечения, не требуя этих функций.

С другой стороны, с каждой итерации графа и каждой глубины рекурсии вычисленной вперед, не только может быть принято решение , будет ли программа остановить или нет, но это будет остановить.

gnasher729
источник
-1

я знаю, что это не формально правильный ответ, но как только вы возьмете «минимальное» из «полного по Тьюрингу» и вернете «практическое» туда, где оно принадлежит, вы увидите самые важные функции, которые отличают язык программирования от язык разметки

  • переменные
  • условные (если / тогда ...)
  • loopage (loop / break, пока ...)

следующий пришел

  • анонимные и именованные функции

Чтобы проверить эти утверждения, начните с языка разметки, скажем, HTML. мы могли бы изобрести HTML + только с переменными или только с условными (MS сделал это с условными комментариями), или с какой-то конструкцией цикла (которая в отсутствие условных выражений, вероятно, в конечном итоге выглядела бы как нечто подобное <repeat n='4'>...</repeat>). выполнение любого из них сделает HTML + значительно (?) более мощным, чем обычный HTML, но это все равно будет больше разметки, чем языка программирования; с каждой новой функцией вы делаете ее менее декларативной и более императивной.

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

опять же, я никогда не заканчивал свою CS.

течь
источник
2
Если вы не уверены, вы должны исследовать это в первую очередь. fractran является Тьюринга , как BrainF * ск . Также обратите внимание, что HTML 5 + CSS 3 завершен по Тьюрингу, поскольку он может реализовать правило 110 .
1
Да, да, я знаю. но все приведенные примеры более или менее эзотеричны (хотя, может быть, интересны или удивительны), мой ответ был прагматичным и, скорее всего, вовсе не минимальным. я думаю, что важно указать на это - эта страница была # 1 при поиске полноты по Тьюрингу в Google, ответы здесь - ИМХО мало полезны, скажем, для новичка, который хочет знать, что отличает HTML от PHP или Python. я имею в виду, что brainf ck не называется brainf ck без причины.
поток