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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Решение задач

 

Задача 4.Машина Поста

Правила игры Баше: на ленте  имеется последовательность из 21 метки. В начале игры головка расположена  над крайней левой меткой. Игроки (машина Поста и вы) поочередно сдвигают головку вправо на 1, 2, 3 или 4 ячейки. Первый ход у вас. Проигрывает тот, кто первым достигает конца последовательности. Напишите программу для МП, по которой она будет выигрывать.

Решение:

Начинать с крайней  левой

Для каждого хода запускать  заново! 

1 С 2 2 → 3 3 → (4, 2) 4 ← 5 5 → (49, 6) 6 ← 7 7 → (50, 8) 8 ← 9 9 → (51, 10) 10 ← 11

11 → (51, 12) 12 ← 13 13 → (44, 14) 14 ← 15 15 → (49, 16) 16 ← 17 17 → (50,18) 18 ← 19 19 → (51, 20) 20 ← 21

21 → (44, 22) 22 ← 23 23 → (49, 24) 24 ← 25 25 → (50, 26) 26 ← 27 27 → (51, 28) 28 ← 29 29 → (44, 30) 30 ← 31

31 → (49, 32) 32 ← 33 33 → (50, 34) 34 ← 35 35 → (51, 36) 36 ← 37 37 → (44, 38) 38 ← 39 39 → (49, 40) 40 ← 41

41 → (50, 42) 42 ← 43 43 → (51, 44) 44 M 45 45 → 46 46 → 47 47 → 48 48 → 52 49 M 46 50 M 47 51 M 48 52 СТОП 52

 

 

 

 

 

 

 

 

Задача 4. Машина Тьюринга

На ленте машины Тьюринга задана последовательность из символов двоичного алфавита. Необходимо переместить  все нули в начало строки, а единицы  – в конец.

Решение:

Начальное положение головки– над крайней левой меткой

A\Q	Q0	Q1	Q2	Q3
1	1>0	0>2
0	0<1	0>3	1<0	0<0
Пробел	_!0	_>3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

Машина Поста — это абстрактная (т.е. не существующая в арсенале действующей  техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее  на машине Поста можно запрограммировать  — в известном смысле — любые  алгоритмы. Изучение машины Поста можно  рассматривать как начальный  этап обучения теории алгоритмов и  программированию. Разработка программ для машин Поста — достаточно эффективный этап в обучении алгоритмизации, т.к. в процессе написания этих программ учащиеся учатся разбивать интуитивно понятные вычислительные процедуры  на элементарные действия. Изучение машины Поста полезно как школьникам, интересующимся информатикой и математикой, так и студентам младших курсов, обучающимся по специальности “прикладная  математика и информатика”.

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

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

В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.  
 

СПИСОК ЛИТЕРАТУРЫ

 

1.  Авдеев Р.Ф. Философия информационной цивилизации [Текст] / Р.Ф. Авдеев. – М.: ВЛАДОС, 2008.

2.  Булгаков И.С. Счетные машины [Текст] / И.С. Булгаков. – М.: Машгиз, 2010.

3.  Ершов Ю.Л. Математическая логика [Текст] / Ю.Л. Ершов, Е.А. Палютин. – М.: Наука, 2008.

4.  Клини С. Введение в метаматематику [Текст] / С. Клини. – М.: Изд-во иностр. лит., 2008.

5.  Клини С. Машины Тьюринга и рекурсивные функции [Текст] / С. Клини. – М., 2010.

6.  Колин, К.К. Фундаментальные основы информатики: социальная информатика [Текст]: учеб. пособие для вузов / К.К. Колин. – М.: Академический Проект; Екатеринбург: Деловая книга, 2008.

7.  Поликарпов В.С. История науки и техники [Текст]: учеб. пособие / В.С. Поликарпов. – Ростов Н/Д: Феникс, 2008.

8.  Успенский В.А. Машина Поста [Текст] / В.А. Успенский. – М.: Наука, 2010. – 96 с.

9.  Успенский В.А. Теория алгоритмов: основные открытия и приложения [Текст] / В.А. Успенский, А.Л. Семенов. – М.: Наука, 2010. – 288 с.