Существует много (и я имею в виду много) исчисляемых языков, которые разрешимы по Тьюрингу. Может ли любой бесчисленный язык быть разрешимым по Тьюрингу?
formal-languages
turing-machines
regular-languages
church-turing-thesis
Йотирмой Праманик
источник
источник
Ответы:
Каждый язык над конечным (или даже счетным) алфавитом исчисляется. Предполагая, что ваш алфавит машины Тьюринга конечен, любой язык, который он может принять, является исчисляемым.
источник
Мы можем иметь бесчисленные языки, только если мы допустим слова бесконечной длины, см., Например, омега-регулярный язык . Эти языки называются языками. Другим примером будет язык подмножеств вещественных чисел, который содержит, скажем, десятичные разложения всех действительных чисел.ω
Есть некоторые модели, в которых машины Тьюринга модифицированы для принятия языков. Некоторые из этих моделей используют условие Бучи для принятия. Поскольку вы не можете увидеть весь ввод за конечное время, мы говорим, что ввод принят, если машина Тьюринга входит в состояние принятия бесконечно много раз. Если мы можем доказать это, проанализировав ввод (не запустив его), мы скажем, что ввод принят.ω
источник
Классическая вычислимость обсуждает функции над конечными строками из конечного алфавита. В результате все языки, разрешимые или неразрешимые, являются исчисляемыми.
Чтобы рассмотреть несчетные языки, мы должны смотреть на бесконечные строки вместо конечных строк. (AFAIK, имея бесконечный алфавит, не очень интересен и сам по себе не соответствует реалистичной модели вычислений.)
Существуют модели вычислений, в которых мы можем иметь дело с бесконечными строками, которые позволяют нам представлять объекты из неисчислимых областей, таких как действительные числа. Они часто представляются как вычисления более высокого типа. Одной из моделей, которая использует машины Тьюринга, является модель TTE. В этой модели входными данными могут быть бесконечные строки, и машины могут получить доступ к любому элементу в нужной строке. Машина не нуждается в завершении, однако существуют условия, чтобы убедиться, что производительность машины сходится.
Предположим, что вход нашей машины от , т.е. от бесконечных строк из алфавита Σ , например Σ = { 0 , 1 } . Тогда есть Σ N = 2 N строк. Поэтому существует 2 2 N возможных языков. Количество машин TTE Turing по-прежнему исчисляется. Поэтому большинство этих языков неразрешимы.Σω Σ Σ={0,1} ΣN=2N 22N
Но здесь есть кое-что еще более интересное: если вы хотите, чтобы машина всегда останавливалась, она сможет прочитать только конечную начальную часть ввода. В результате мы имеем следующее: Пусть будет машинами TTE, которые всегда останавливаются (за конечное время). Тогда есть префикс-свободного язык L ∈ Е * и машина Тьюринга Н , такое , что для любого х ∈ Х ш , М принимает й тогда и только тогда Н принимает начальную часть х , который находится в L .M L∈Σ∗ N x∈Σω M x N x L
Проще говоря, вычисление машин TTE Тьюринга, которые всегда останавливаются, определяется вычислением машины Тьюринга на конечных строках.
Позвольте мне привести некоторые примеры разрешимых и неразрешимых языков бесконечных строк:
Для любого язык бесконечных строк, чья k- я позиция равна 0, разрешим. То же самое с k- й позицией, равной 1. Пересечение любых двух разрешимых языков разрешимо, например, строки, чья 3- я позиция равна 0, а 6- я позиция равна 1.k∈N k k 3 6
Объединение любых двух разрешимых языков разрешимо. Например, строки, начинающиеся с или 10 .0 10
Пусть - вычислимо перечислимый список разрешимых языков. Тогда L = ∪ я L я пол-разрешим, то есть машина , которая останавливается и принимает всякий раз , когда строки в L и не принимает , когда струны не в L . Если его нет в L, машина может не остановиться. Любой полуразрешимый язык может быть получен путем объединения перечислимого списка языков в форме, приведенной в пункте 1 выше.Li L=∪iLi L L L
Язык разрешим, если и язык, и его дополнение являются полуразрешимыми.
источник