Есть ли неисчислимый разрешимый язык Тьюринга?

17

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

Йотирмой Праманик
источник
2
Если язык всех возможных слов неисчислим (что требует бесчисленного алфавита), то он немедленно предоставляет пример (тривиально) разрешимого неисчислимого языка Тьюринга. Если это не так (то есть, оно исчисляется), то и подъязыки не являются неисчисляемыми.
Марк ван Леувен

Ответы:

25

Каждый язык над конечным (или даже счетным) алфавитом исчисляется. Предполагая, что ваш алфавит машины Тьюринга конечен, любой язык, который он может принять, является исчисляемым.

Юваль Фильмус
источник
А как насчет множества всех языков с конечным числом строк над счетно-бесконечным алфавитом? Это исчисляемо или неисчислимо? Также я не смог придумать доказательства того, что «язык над счетно-бесконечным алфавитом исчисляем».
Ани
Ваш набор также исчисляется.
Ювал
Это доказывает, что «множество языков над конечным алфавитом исчисляется». Я чувствую, что мы можем доказать, что «множество языков, содержащих счетные бесконечные строки над конечным алфавитом, исчисляемо», следуя тому же подходу доказательства из-за конечного алфавита. Но я не могу представить, как этот подход можно адаптировать для счетного алфавита.
Ани
Вы не можете доказать это, поскольку это ложь. Число бесконечных двоичных последовательностей уже неисчислимо.
Юваль
12

Мы можем иметь бесчисленные языки, только если мы допустим слова бесконечной длины, см., Например, омега-регулярный язык . Эти языки называются языками. Другим примером будет язык подмножеств вещественных чисел, который содержит, скажем, десятичные разложения всех действительных чисел.ω

Есть некоторые модели, в которых машины Тьюринга модифицированы для принятия языков. Некоторые из этих моделей используют условие Бучи для принятия. Поскольку вы не можете увидеть весь ввод за конечное время, мы говорим, что ввод принят, если машина Тьюринга входит в состояние принятия бесконечно много раз. Если мы можем доказать это, проанализировав ввод (не запустив его), мы скажем, что ввод принят.ω

Shreesh
источник
1
Почему алфавит должен быть исчисляемым?
оставил около
2
Каждая изучаемая модель имеет конечный алфавит. Если алфавит также становится бесконечным (исчисляемым или неисчисляемым), трудно найти разумную модель.
Шреш,
@Shreesh Ну, если алфавит неисчислим, наивное отображение FSM (с неисчислимыми переходами между конечным числом состояний) может быть довольно мощным?
Якк
1
Правда, это такие расширения, которые могут иметь языковые классы, которые могут быть суперклассом RE или рекурсивными языками. Но они плохо изучены, если изучены вообще. Самая большая проблема, на мой взгляд, как мы можем дать конечное представление о машине. Затем вы должны написать символ в ячейке ленты. Даже скромная ячейка может нуждаться в бесконечной памяти для хранения описания записываемого символа ленты.
Shreesh
Это отличное объяснение. Я хотел бы добавить, что даже если используется обычный критерий принятия / отклонения, можно сказать, что все еще существуют некоторые языки, которые машина Тьюринга могла бы выбрать, и с технической точки зрения у нее было бы несчетное количество строк, но только потому, что подавляющее большинство символов " бесполезно "для языка.
Оуэн
5

Классическая вычислимость обсуждает функции над конечными строками из конечного алфавита. В результате все языки, разрешимые или неразрешимые, являются исчисляемыми.

Чтобы рассмотреть несчетные языки, мы должны смотреть на бесконечные строки вместо конечных строк. (AFAIK, имея бесконечный алфавит, не очень интересен и сам по себе не соответствует реалистичной модели вычислений.)

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

Предположим, что вход нашей машины от , т.е. от бесконечных строк из алфавита Σ , например Σ = { 0 , 1 } . Тогда есть Σ N = 2 N строк. Поэтому существует 2 2 N возможных языков. Количество машин TTE Turing по-прежнему исчисляется. Поэтому большинство этих языков неразрешимы.ΣωΣΣ={0,1}ΣN=2N22N

Но здесь есть кое-что еще более интересное: если вы хотите, чтобы машина всегда останавливалась, она сможет прочитать только конечную начальную часть ввода. В результате мы имеем следующее: Пусть будет машинами TTE, которые всегда останавливаются (за конечное время). Тогда есть префикс-свободного язык L Е * и машина Тьюринга Н , такое , что для любого х Х ш , М принимает й тогда и только тогда Н принимает начальную часть х , который находится в L .MLΣNxΣωMxNxL

Проще говоря, вычисление машин TTE Тьюринга, которые всегда останавливаются, определяется вычислением машины Тьюринга на конечных строках.


Позвольте мне привести некоторые примеры разрешимых и неразрешимых языков бесконечных строк:

  1. Для любого язык бесконечных строк, чья k- я позиция равна 0, разрешим. То же самое с k- й позицией, равной 1. Пересечение любых двух разрешимых языков разрешимо, например, строки, чья 3- я позиция равна 0, а 6- я позиция равна 1.kNkk36

  2. Объединение любых двух разрешимых языков разрешимо. Например, строки, начинающиеся с или 10 .010

  3. Пусть - вычислимо перечислимый список разрешимых языков. Тогда L = я L я пол-разрешим, то есть машина , которая останавливается и принимает всякий раз , когда строки в L и не принимает , когда струны не в L . Если его нет в L, машина может не остановиться. Любой полуразрешимый язык может быть получен путем объединения перечислимого списка языков в форме, приведенной в пункте 1 выше.LiL=iLiLLL

  4. Язык разрешим, если и язык, и его дополнение являются полуразрешимыми.

  5. kk


xlgxxlgx нам.


f{0,1}f1(1)". На веб-сайте также есть много других ссылок на вычислимость и сложность в аналитической сети .

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