Счетчик (информатика)

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

Формальное определение

Счетчик $E$ можно определить как двухленточную машину Тьюринга ( многоленточную машину Тьюринга , где $k=2$) чей язык $\emptyset$. Изначально, $E$ не получает никаких входных данных, и все ленты пусты (т. е. заполнены пустыми символами). Новый определенный символ $\#\in \Gamma \land \#\notin \Sigma$ разделитель, который отмечает конец элемента $S$. Вторую ленту можно рассматривать как принтер, строки на ней разделены $\#$. Язык, перечисляемый перечислителем $E$ обозначается $L(E)$ определяется как набор строк на второй ленте (принтере).

Эквивалентность перечислителя и машины Тьюринга

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

Доказательство

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

Рассмотрим машину Тьюринга $M$ и язык, принятый им, будет $L(M)$. Поскольку множество всех возможных строк во входном алфавите $\Sigma$ то есть замыкание Клини $\Sigma ^{*}$ является счетным множеством, мы можем перечислить строки в нем как $s_{1},s_{2},\dots ,s_{i},$ и т. д. Затем Enumerator, перечисляющий язык $L(M)$ будет следовать шагам:

1 for i = 1,2,3,...
2 Run $M$ with input strings $s_{1},s_{2},\dots ,s_{i}$ for $i$-steps
3 If any string is accepted, then print it. 

Теперь возникает вопрос, каждая ли строка в языке $L(M)$ будет напечатан созданным нами перечислителем. Для любой строки $w$ на языке $L(M)$ ТМ $M$ выполнит конечное число шагов (пусть это будет $k$ для $w$), чтобы принять это. Затем в $k$-й шаг перечислителя $w$ будет напечатан. Таким образом, Enumerator будет печатать каждую строку $M$ распознает, но одна строка может быть напечатана несколько раз.

Перечислимый язык узнаваем по Тьюрингу

Построить машину Тьюринга очень легко. $M$ который распознает перечислимый язык $L$. У нас может быть две кассеты. На одной ленте мы берем входную строку, а на другой — запускаем перечислитель для перечисления строк в языке одну за другой. Как только строка напечатана на второй ленте, мы сравниваем ее с входными данными на первой ленте. Если совпадение, мы принимаем входные данные, иначе отклоняем.

Ссылки

• Сипсер, Майкл (2012). Введение в теорию вычислений - международное издание . Cengage Обучение. ISBN  978-1-133-18781-3 .