Общий язык, который может интерпретировать только полный язык Тьюринга

16

Любой язык, не являющийся полным по Тьюрингу, не может написать для себя интерпретатор. Я понятия не имею, где я это прочитал, но я видел, что это использовалось несколько раз. Кажется, что это порождает своего рода «окончательный» нетуринговский законченный язык; те, которые могут толькоинтерпретироваться машиной Тьюринга. Эти языки не обязательно будут способны вычислять все полные функции от натуральных до натуральных, и при этом они не обязательно будут изоморфными (то есть, возможно, конечные языки A и B существуют так, что существует функция F, которую A может вычислять, но B не может). Агда может интерпретировать систему Т Годеля, а Агда является тотальной, так что такой конечный язык должен быть строго более мощным, чем могло бы показаться системе Т Годеля. Мне кажется, что такой язык был бы по крайней мере таким же мощным, как и агда (хотя у меня нет доказательств, только догадка).

Было ли проведено какое-либо исследование в этом направлении? Какие результаты известны (а именно такой «конечный» язык известен)?

Бонус: я обеспокоен тем, что существует патологический случай, который не может вычислить функции, которые System T Годеля еще может интерпретировать только машиной Тьюринга, поскольку она позволяет вычислять некоторые действительно странные функции. Так ли это, или мы можем знать, что такой язык сможет вычислять все, что может вычислить Godel System T?

Джейк
источник
2
Ваши заявления сбивают с толку из-за того, как вы используете терминологию. Вместо того чтобы полагаться на терминологию, постарайтесь изложить ваш вопрос математически строго и четко, чтобы мы могли понять ваш вопрос. Что вы подразумеваете под языком программирования в контексте теории вычислимости? Вы имеете в виду перечисление вычислимых функций?
Каве
1
Я думаю о том, что вы читаете: если язык достаточно силен и содержит универсальную функцию другого класса функций, он может определить диагональную функцию для этого класса. Если это класс тотальных функций, то диагональная функция не может быть в этом классе.
Каве
Там было указано неофициально, где я его нашел. Что-то буквально в соответствии с тем, что я дал здесь. Я тоже не знаю, как это выразить математически. После некоторого прочтения я не уверен, что такое «диагональная функция класса функций». Я думаю, что в ваших терминах я имею в виду, что «класс тотальных функций не может содержать свою собственную универсальную функцию», и поэтому я думаю, что я спрашиваю «для какого класса тотальных функций C это тот случай, когда ни один класс тотальных функций не содержит универсальная функция для C ". Если я понимаю, что такое «универсальная функция», я думаю, что это правильно.
Джейк
1
Строго говоря, это не вопрос исследовательского уровня. Кроме того, почему это вики сообщества? Или это?
Андрей Бауэр
«Кажется, что это порождает своего рода« окончательный », не истинный, полный язык; тот (ие), который может быть интерпретирован только машиной Тьюринга». не следуйте этому утверждению, оно кажется не последовательным, что вы имеете в виду, почему это так кажется?
августа

Ответы:

42

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

Пусть быть функцией спаривание .м,N

Допустим, что язык программирования задается следующими данными:Lзнак равно(п,еv)

  1. разрешимо множество из «действующих программ», ипN
  2. вычислимы и частичная функция .еv:п×NN

Тот факт, что разрешимо, означает, что существует полное вычислимое отображение v a l i d : N{ 0 , 1 } такое, что v a l i d ( n ) = 1пvaLяd:N{0,1} . Неформально мы говорим, что можно определить, является ли данная строка допустимым фрагментом кода. Функция e v по сути является интерпретатором для нашего языка: e v ( m , n ) выполняет код m на входе n - результат может быть неопределенным.vaLяd(N)знак равно1Nпеvеv(м,N)мN

Теперь мы можем ввести некоторую терминологию:

  1. Язык является всего , если является полной функцией для всех м P .Nеv(м,N)мп
  2. Язык интерпретирует язык L 2 = ( Р 2 , е v 2 ) , если существует у Р 1 таким образом, что е v 1 ( U , п , м ) е v 2 ( n , m ) для всех n PL1знак равно(п1,еv1) L2знак равно(п2,еv2)Uп1еv1(U,N,м)еv2(N,м)Nпи . Здесь u - симулятор для L 2, реализованный в L 1 . Он также известен как универсальная программа для L 2 .мNUL2L1L2

Возможны и другие определения « интерпретирует L 2 », но позвольте мне не вдаваться в подробности.L1L2

Мы говорим, что и L 2 эквивалентны, если они интерпретируют друг друга.L1L2

Существует «самый мощный» язык машин Тьюринга (который вы называете «машиной Тьюринга»), в котором n N - это кодировка машины Тьюринга, а φ ( n , m ) - частично вычислимая функция, которая «запускает машину Тьюринга, кодирующую n на входе m ». Этот язык может интерпретировать все другие языки, очевидно, так как мы требовали, чтобы e v была вычислимой.Tзнак равно(N,φ)NNφ(N,м)Nмеv

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

  • реализует функцию-преемник: существует такое s u c c P , что e v ( s u c c , m ) = m + 1 для всех m N ,LsUсспеv(sUсс,м)знак равном+1мN
  • реализует диагональ функция: есть d I в г P такоечто е V ( д я г , т ) = м , м для всех м N ,Ldяaграммпеv(dяaграмм,м)знак равном,ммN
  • замкнуто относительно композиции функций: если L реализует f и g, то оно также реализует f g ,LLеграммеграмм

Классический результат таков:

Теорема: если язык может интерпретировать сам себя, то он не тотален.

Доказательство. Предположим , что является универсальная программа для полного LANGAUGE L , реализованного в L , то есть, для всех т Е Р и п Е N , е V ( U , м , п ) е v ( т , п ) . Как преемник, диагональ, и e v ( u , - ) реализованы в L , так же как и их композиция k ULLмпNN

еv(U,м,N)еv(м,N),
еv(U,-)L . Там существует п 0P такоечто е v ( п 0 , к ) е V ( U , к , к ) + 1 , а затем е V ( U , п 0 , п 0) е v (Кеv(U,К,К)+1N0пеv(N0,К)еv(U,К,К)+1 Поскольку существует число не равна его собственного преемника, то отсюда следуетчто L не является полным иличто L не интерпретирует себя. QED.
еv(U,N0,N0)еv(N0,N0)еv(U,N0,N0)+1
LL

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

Вот небольшая теорема, которая, я думаю, устранит недоразумение.

Теорема. Каждый общий язык может быть интерпретирован другим общим языком.

Доказательство. Пусть тотальный язык. Мы получаем итоговое значение L ′, которое интерпретирует L , присоединяя к L его вычислитель e v . Точнее, пусть Р ' = { 0 , п | п P } { 1 , 0 } и определим е V ' , как е V ' ( б , н , мLL'LLеvп'знак равно{0,N|Nп}{1,0}еv' Очевидно, что L ' является полнымпотому что L является полным. Для того, чтобы видетьчто L ' может имитировать L просто взять у = 1 , 0

еv'(б,N,м)знак равно{еv(N,м)если бзнак равно0,еv(м0,м1)если бзнак равно1 и мзнак равном0,м1
L'LL'L , С тех пор е V ' ( U , м , н ) е V ( т , п ) ,мере необходимости. QED.Uзнак равно1,0еv'(U,м,N)еv(м,N)

Упражнение: [добавлено 2014-06-27] Построенный выше язык не замкнут по составу. Закрепить доказательство теоремы , так что L ' удовлетворяет дополнительные требования , если L делает.L'L'L

Другими словами, вам никогда не понадобится вся мощь машин Тьюринга для интерпретации общего языка - достаточно более мощного общего языка L . Язык L строго более мощный, чем L, потому что он интерпретирует L , но L не интерпретирует себя.LL'L'LLL

Андрей Бауэр
источник
Если я установил флажок вики, это было непреднамеренно.
Андрей Бауэр
2
Существуют ли какие-либо дополнительные возможности в языках, когда вы не можете определить, является ли данная программа действительной?
Phylliida
3
@DaniPhye: Если синтаксис языка не является полуразрешимым, вы можете «скрыть» вычислительную мощь в синтаксисе. Например, языковые правила могут требовать, чтобы каждая функция была снабжена битом, который сообщает, является ли функция полной. Затем мы могли бы реализовать is_total, что в противном случае некомпьютеризуемо, но не может реализовать оценку (потому что вам также придется вычислять бит результирующей функции). В общем, я бы сказал, что это не язык программирования, если вы не можете даже реализовать для него парсер.
Андрей Бауэр
3
Как гель «Если язык может интерпретировать сам себя, тогда он не тотален» с таким результатом: Самопереводчик для F-omega ?
Кактус
2
Вот так
Андрей Бауэр
18

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

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

Дэвид Ричерби
источник
Ах! Это хороший момент. Поэтому должны быть определенные требования к тому, что язык вычисляет. Похоже, что для того, чтобы сделать это утверждение верным, необходимо сделать какое-то минимальное требование в отношении силы языка. Кажется, что если мы требуем, чтобы это было в состоянии решить основные арифметические проблемы, то это могло бы иметь место.
Джейк
@ Джейк Вы могли бы действительно быть в состоянии избежать неприятностей с чем-то невероятно слабым, например, «язык определяет хотя бы одну непостоянную функцию» или «язык определяет более одной функции». Мой контрпример явно тривиален для любого разумного определения «тривиально».
Дэвид Ричерби
Похоже, интересная проблема для меня, чтобы думать. Если я найду что-нибудь, я отвечу обратно.
Джейк