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

Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, … . В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = {L, a1, a2 ,..., an-1 }, n ³ 2 . Пустая ячейка обозначается символом L, а сам символ L называется пустым, при этом остальные символы называются непустыми

1. Математическая модель машины Тьюринга 3

2. Работа машины Тьюринга 6

3. Примеры машин Тьюринга, работающих в алфавите {a, b} 7

4. Способы задания машин Тьюринга, операции над ними 11

5. Список используемой литературы 14