Ищу языки, не являющиеся полными по Тьюрингу
Я немного знаю о том, что такое машина Тьюринга и полный по Тьюрингу язык, но чтобы лучше понять, не мог бы кто-нибудь привести примеры языки, не являющиеся полными по Тьюрингу? (возможно, даже машины, не являющиеся полными по Тьюрингу, тоже?)
2 ответа
Регулярные выражения, в формальном определении, состоящий только из:
- конкатенации (аб)
- неограничена повторение (а *)
- Чередование (а | б)
- группировка ((аb) | (кд))
может распознавать только регулярные языки.Тьюринг-полный язык программирования может распознавать рекурсивно-перечислимые языки.
Например, регулярные выражения не могут сказать вам, состоит ли строка из совпадающих пар скобок: например, ()(()) принимается, а ()((())() отвергается, в то время как полные по Тьюрингу языки программирования могут
(Обратите внимание, что регулярные выражения в современных языках программирования более эффективны, чем формальное академическое определение регулярных выражений. Некоторые из них могут быть даже полными по Тьюрингу.)
Обычные языки — те, которые можно описать как регулярные выражения — не полны по Тьюрингу.
Языки разметки (используемые для описания данных, а не вычислений), такие как XML и JSON, не являются полными по Тьюрингу.