ddd

Машина Тьюринга

Данная статья посвящена, простому объяснению.

Как и по какому принципу действует машина Тьюринга.

Фундаментальные понятия:

Q1-2R

q-это просто идентификатор

1 – состояние

2- буква из заданного алфавита на которую необходимо заменить

R- это идентификатор говорящий куда ему необходимо идти (R-направо, L – налево, S – стоп)

2. Сама машина представляет собой некую ленту на которой размещается слово.

(1,0,1,0,0) у каждой буквы есть свое состояние. Оно заранее описано.

И существует таблица в которой задается состояние и буквы алфавита. И на пересечении состояния и буквы алфавита стоит правило по которому действует в дальнейшем машина.

Я думаю, что для большего понимания надо почитать книгу по дискретной математике. Например: С.В. Яблонский “Введение в дискретную математику”