Все ли тьюринговые полные языки взаимозаменяемы

Обратите внимание, хотя я знаю, как программировать, я довольно новичок в теории CS.

Согласно этому ответу

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

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

Хорошо. Это имеет смысл. Я могу перевести (скомпилировать) C в Assembly (и я делаю это каждый день!), И могу перевести Assembly в C (Вы можете написать виртуальную машину на C). И то же самое относится к любому другому языку - вы можете скомпилировать любой язык в Assembly, а затем запустить его на виртуальной машине, написанной на другом языке.

Но может ли какая-либо программа, написанная на полном языке Тьюринга, быть переписана на другом языке?

Что если моя сборка имеет код операции LIGHTBUTTON? Я физически не могу подражать этому языку в системе (языке) без лампочки.

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

Но как насчет устройства, которое не имеет умножения? разделение? Насколько я знаю (хотя это больше вопрос для математики. SE), никто не может эмулировать умножение (и определенно не деление) с сложением и вычитанием [1].

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

РЕДАКТИРОВАТЬ

[1]. На произвольных действительных числах.

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

Итак, какие вычисления может смоделировать машина Тьюринга? Ну, во-первых, Алан Тьюринг и все его коллеги интересовались только функциями с натуральными числами. Таким образом, машина Тьюринга (и λ-исчисление, исчисление комбинаторов SK, μ-рекурсивные функции…) говорят только о вычислимости функций на натуральных числах. Если вы не говорите о функции на натуральных числах, то концепция полноты по Тьюрингу даже не имеет смысла, она просто не применима.

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

И, конечно же, не все функции на натуральных числах вычислимы. Машина Тьюринга может вычислять только некоторые функции на натуральных числах, λ-исчисление может вычислять только некоторые функции на натуральных числах, исчисление комбинатора SK может вычислять только некоторые функции на натуральных числах,…. Удивительно (или нет), оказывается, что каждая модель вычислений (которая фактически реализуема в нашей физической вселенной) может вычислять те же функции на натуральных числах (по крайней мере для всех моделей, которые мы до сих пор находили). [Примечание: очевидно, что существуют более слабые модели вычислений, но мы еще не нашли более сильную модельза исключением тех, которые явно несовместимы с нашей физической вселенной, такие как модели, использующие реальные числа или путешествия во времени.]

Этот факт, что после долгого времени поиска для множества различных моделей, мы находим, каждый раз, что они могут вычислить точно те же функции, является основой для Черча-Тьюринга-Thesis, в котором говорится (грубо) , что все Модели вычислений одинаково мощны, и все они отражают «идеальное» понятие того, что значит быть «вычислимым». (Существует также второй, более философский аспект CTT, а именно, что человек, следуя алгоритму, может также вычислять точно такие же функции, которые может вычислять TM, и не более.)

Тем не менее , ничего из этого не говорит о

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

И что именно там , где различие между различными моделями вычислений (и языков программирования) вступает в игру.

В качестве примера различной производительности, как машина произвольного доступа, так и машина Тьюринга могут копировать массив. Но для этого в ОЗУ необходимы в то время как для ТМ нужны , поскольку для копирования каждого элемента необходимо пропускать массива. и есть элементы для копирования.$O(size_{array})$$O(size_{array}^2)$$size_{array}$$size_{array}$

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

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

Чтобы ответить на ваши конкретные вопросы:

Но может ли какая-либо программа, написанная на полном языке Тьюринга, быть переписана на другом языке?

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

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

Что если моя сборка имеет код операции LIGHTBUTTON? Я физически не могу подражать этому языку в системе (языке) без лампочки.

Лампочка не является вычислимой по Тьюрингу функцией натуральных чисел. Действительно, лампочка не является ни функцией, ни вычислением. Включение и выключение лампочки является побочным эффектом ввода / вывода. Машины Тьюринга не моделируют побочные эффекты ввода / вывода, и Turing-completess к ним не относится.

На произвольных действительных числах.

Полнота Тьюринга имеет дело только с вычислимыми функциями на натуральных числах, она не касается реальных чисел.

Полнота Тьюринга просто не очень интересна, когда речь идет о таких вопросах, как ваш, по двум причинам:

1. Это не очень высокое препятствие. Все , что вам нужно , это IF, GOTO, WHILEи одно целое число переменной (предполагается , что переменная может содержать сколь угодно большие целые числа). Или рекурсия. Много-много-много всего полно Тьюринга. Карточная игра Magic: The Gathering завершена по Тьюрингу. CSS3 завершен по Тьюрингу. sendmailФайл конфигурации Тьюрингу. Intel x86 MMU является полным по Тьюрингу. MOVИнструкция Intel x86 завершена по Тьюрингу. Анимации PowerPoint завершены по Тьюрингу. Excel (без сценариев, только с использованием формул) является полным по Тьюрингу. Протокол маршрутизации BGP является полным по Тьюрингу. sedзавершена по Тьюрингу. mod_rewriteПравила Apache полны по Тьюрингу. Google для " (случайно или удивительно) завершения"чтобы найти другие интересные примеры. Если почти все является полным по Тьюрингу, то полное отсутствие по Тьюрингу перестает быть интересным свойством.
2. На самом деле нет необходимости быть полезным. Много полезных вещей не завершено по Тьюрингу. CSS до версии 3 не Тьюринг-полной (и тот факт , что CSS3 является на самом деле не используется кем - либо). SQL до 1999 года не был полным по Тьюрингу, но даже тогда он был чрезвычайно полезен. Язык программирования C без дополнительных библиотек не кажется завершенным по Тьюрингу . Языки с независимой типизацией, более или менее по определению, не являются полными по Тьюрингу, но в них можно писать операционные системы, веб-серверы и игры.

Эдвин Брэди, автор Idris, использует термин «Tetris-complete», чтобы говорить о некоторых из этих аспектов. Быть полным тетриса не является строго определенным (кроме очевидного «может использоваться для реализации тетриса»), но оно включает в себя такие вещи, как быть достаточно высокоуровневым и достаточно выразительным, чтобы вы могли написать игру, не сходя с ума, имея возможность взаимодействовать с внешним миром (вход и выход), быть способным выражать побочные эффекты, уметь писать цикл событий, уметь выражать реактивное, асинхронное и параллельное программирование, уметь взаимодействовать с операционной системой, уметь взаимодействовать с иностранными библиотеками (другими словами: возможность вызывать и вызываться кодом C) и так далее. Это гораздо более интересные особенности языка программирования общего назначения, чем полнота по Тьюрингу.

Вы можете найти мой ответ на интересующий вас вопрос интересным, затрагивающим одни и те же вопросы, даже если он отвечает на другой вопрос.

Конечно, вы можете реализовать умножение с сложением и вычитанием:

/* Assume b is positive for simplicity */
int multiply(int a, int b) {
  int res = 0;
  while (b > 0) { res += a; b -= 1; }
  return res;
}

Тот факт, что вы, скорее всего, этого не сделаете, не делает это менее вероятным.

Деление чуть сложнее

/* Assume a and b are positive for simplicity */
int divide(int a, int b) {
  int res = 0;
  while (a >= b) { res += 1; a -= b; }
  return res;
}

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

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

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

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

Вы можете реализовать умножение и деление как повторное сложение и вычитание соответственно, наблюдая, что и .m / n = 1 + ( m - n ) /$nm = n + n(m-1)$$m/n = 1 + (m-n)/n$

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

Также возможно реализовать их таким образом, чтобы сохранить вычислительную сложность. Прежде всего, обратите внимание, что умножение на является «свободным» ( ). Используя умножение на , цикл и вычитание, мы можем легко реализовать евклидов алгоритм для деления на два. С умножением и делением на два, мы можем реализовать русский алгоритм умножения, наблюдая, что и . С произвольным умножением мы можем наконец реализовать полный евклидов алгоритм для деления.2 n = n + n 2 m × 2 n = 2 m × n m × ( 2 n + 1 ) = m + 2 m × $2$$2n = n+n$$2$$m \times 2n = 2m \times n$$m \times (2n+1) = m + 2m \times n$

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

Что если моя сборка имеет код операции LIGHTBUTTON? Я физически не могу подражать этому языку в системе (языке) без лампочки.

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

Таким образом, машина Тьюринга будет отвечать за создание строки "LIGHTBUTTON"или некоторого целочисленного значения, соответствующего этому коду операции; действует ли на него внешняя сущность, это не дело компьютера Тьюринга.

Программы на C имеют такое же ограничение. Это означает, что программа на С может вызывать только код операции LIGHTBUTTON, однако, действительно ли ЦП выполняет операцию, связанную с этим кодом операции, до ЦП.

Но как насчет устройства, которое не имеет умножения? разделение? Насколько я знаю (хотя это больше вопрос для математики. SE), никто не может эмулировать умножение (и определенно не деление) с сложением и вычитанием [на произвольных действительных числах].

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

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

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

Фактически, вы можете делать реальные вычисления на машинах Тьюринга! Чтобы продемонстрировать это, вот WolframAlpha, вычисляющая . Я имею в виду, конечно, машины Тьюринга не могут бесконечно расширять за конечное время, но это нормально; никто не бесконечно расширяет , в том числе и людей. Но если мы приписываем людям математику с действительными числами, например, , то мы должны отдать должное машинам Тьюринга.$\pi-\pi=0$π π - π = $\pi$$\pi$$\pi-\pi=0$

Но может ли какая-либо программа, написанная на полном языке Тьюринга, быть переписана на другом языке?

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

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

• они поддерживают различные виды ввода и вывода (например, доступ к базе данных SQL)

• у них есть разные библиотеки типов данных (например, поддержка строк Unicode)

• они предоставляют различные парадигмы программирования, оптимизированные для различных задач (например, объекты, потоки, сопрограммы, первоклассные функции)

• они предоставляют различные библиотеки функций (например, анализ XML и сериализация)

Нет. Тьюринг-полнота не имеет ничего общего с программами , она касается математических функций (или алгоритмов ). Любой алгоритм - любое вычисление - вы можете сделать на C, вы можете сделать на любом другом языке, полном Тьюринга (это должно быть очевидно). Но полнота по Тьюрингу на самом деле не говорит о том, что вы можете делать ввод / вывод - вообще. Это не говорит об аппаратном обеспечении вообще. Просто вычисления.

Вы можете расширить язык, полный по Тьюрингу, любой аппаратной операцией, которую захотите (технически это так fputcи fgetcработает в C). Если вы возьмете два языка, полного по Тьюрингу, и расширите их с помощью идентичных аппаратно-специфических операций, они останутся взаимозаменяемыми. Таким образом, ваш язык ассемблера с LIGHTBULBработой более мощный, чем Turing-complete; можно сказать, что все по Тьюрингу законченоLIGHTBULB . Чтобы сделать любой другой язык идентичным этому, он также должен быть закончен по Тьюрингу LIGHTBULB; самый простой способ сделать это - добавить к нему LIGHTBULBпримитив / инструкцию / функцию / и т.д.

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