Ищем языки, которые не являются законченными по Тьюрингу - PullRequest
Новая
       78

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

8 голосов
/ 30 августа 2010

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

Ответы [ 2 ]

12 голосов
/ 30 августа 2010

Регулярные выражения в формальном определении, состоящие только из:

  • конкатенация (ab)
  • неограниченное повторение (a *)
  • альтернирование (a |б)
  • группировка ((ab) | (cd))

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

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

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

3 голосов
/ 30 августа 2010

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

Языки разметки (используемые для описания данных, а не вычислений), такие как XML и JSON, не являются завершенными по Тьюрингу.

...