Принимаемый язык и выбранный язык

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

TM определяет язык, принимает ли он его, и входит в состояние отклонения для любого ввода не на этом языке. Язык рекурсивен, если он определяется машиной Тьюринга.

В некоторых случаях TM не останавливается. Такая ТМ принимает язык, но не решает его.

Разработка машины Тьюринга

Основные принципы разработки машины Тьюринга были объяснены ниже с помощью пары примеров.

Пример 1

Разработайте TM для распознавания всех строк, состоящих из нечетного числа α.

Solution

Машина Тьюринга M могут быть построены следующими движениями -

• Позволять q₁ быть начальным состоянием.

• Если M в q₁; при сканировании α он переходит в состояниеq₂ и пишет B (пусто).

• Если M в q₂; при сканировании α он переходит в состояниеq₁ и пишет B (пусто).

• Из приведенных выше ходов мы видим, что M входит в государство q₁ если он просканирует четное число α и перейдет в состояние q₂если он сканирует нечетное количество α. Следовательноq₂ единственное принимающее государство.

Следовательно,

M = {{q ₁ , q ₂ }, {1}, {1, B}, δ, q ₁ , B, {q ₂ }}

где δ определяется как -

Символ алфавита ленты	Текущее состояние 'q 1 '	Текущее состояние 'q 2 '
α	BRq 2	BRq 1

Пример 2

Разработайте машину Тьюринга, которая считывает строку, представляющую двоичное число, и стирает все ведущие 0 в строке. Однако, если строка состоит только из 0, она сохраняет один 0.

Solution

Предположим, что входная строка заканчивается пустым символом B на каждом конце строки.

Машина Тьюринга, M, могут быть построены следующими движениями -

• Позволять q₀ быть начальным состоянием.

• Если M в q₀, при чтении 0 он движется вправо, переходит в состояние q₁ и стирает 0. При чтении 1 он переходит в состояние q₂ и движется вправо.

• Если M в q₁при чтении 0 он перемещается вправо и стирает 0, т. е. заменяет 0 на B. Достигнув крайней левой единицы, он входитq₂и движется вправо. Если он достигает B, т. Е. Строка состоит только из нулей, он перемещается влево и переходит в состояниеq₃.

• Если M в q₂при чтении 0 или 1 он перемещается вправо. Достигнув B, он перемещается влево и входит в состояниеq₄. Это подтверждает, что строка состоит только из нулей и единиц.

• Если M в q₃, он заменяет B на 0, перемещается влево и достигает конечного состояния q_f.

• Если M в q₄при чтении 0 или 1 он перемещается влево. Достигнув начала строки, т.е. когда он читает B, он достигает конечного состоянияq_f.

Следовательно,

M = {{q ₀ , q ₁ , q ₂ , q ₃ , q ₄ , q _f }, {0,1, B}, {1, B}, δ, q ₀ , B, {q _f }}

где δ определяется как -

Символ алфавита ленты	Текущее состояние 'q 0 '	Текущее состояние 'q 1 '	Текущее состояние 'q 2 '	Текущее состояние 'q 3 '	Текущее состояние 'q 4 '
0	BRq 1	BRq 1	ORq 2	-	OLq 4
1	1Rq 2	1Rq 2	1Rq 2	-	1лк 4
B	BRq 1	BLq 3	BLq 4	OLq f	BRq f