Может ли полный язык тьюринга иметь cfg?

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

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

Проще говоря, brainfuck - это обычный полный язык Тьюринга.

user2201041 31.10.2018 11:36

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

Ira Baxter 31.10.2018 16:14
2
2
610
1

Ответы 1

Мы часто неточно используем эти термины, но для правильного ответа на ваш вопрос необходимо, чтобы мы были очень точными в том, как мы используем термины.

Две вычислительные системы - это эквивалент, если они могут моделировать друг друга. Вычислительная система - это Эквивалент Тьюринга, если она эквивалентна Машины Тьюринга.

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

Грамматики BNF описывают контекстно-свободные языки, и наименее способной вычислительной системой, способной анализировать такие языки, является выталкивающие автоматы. Эта вычислительная система не может имитировать Машины Тьюринга в том смысле, что есть вычисления, которые машина Тьюринга может выполнять, а автомат выталкивания не может; следовательно, автоматы выталкивания не являются Эквивалент Тьюринга.

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

В статье НЕ говорится, что TeX эквивалентен Тьюрингу (возможно, это так, а может и нет; я понятия не имею). Как указано в комментарии, полнота представления вычислительной системы по Тьюрингу совершенно не связана с ее эквивалентностью по Тьюрингу. Даже сами машины Тьюринга могут быть представлены с использованием строк обычного языка (фактически, расширяют интерпретацию любого языка, чтобы в противном случае недопустимые программы компилировались в программу, которая останавливается без каких-либо действий, и внезапно ВСЕ строки являются действительными, а язык всех струны конечно обычные).

Другие вопросы по теме