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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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