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

Автор работы: Пользователь скрыл имя, 06 Мая 2012 в 19:29, контрольная работа

Краткое описание

Одним из центральных понятий информатики является понятие алгоритма. Абстрактные (т.е. существующие не реально, а лишь в воображении) машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. американским математиком Эмилем Леон Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой универсальных исполнителей, являющихся полностью детерминированными, позволяющих «вводить» начальные данные, и после выполнения программ «читать» результат.

Содержание работы

ВВЕДЕНИЕ 3
1. 1. Машина Поста. Основные понятия и операции 4
1.2. Способ задания проблемы и формулировка 1 6
2. Машина Тьюринга 8
3.Решение Задач 11
ЗАКЛЮЧЕНИЕ 13
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14

Содержимое работы - 1 файл

Машина Поста. Машина Тьюринга.docx

— 40.33 Кб (Скачать файл)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 с.


Информация о работе Машина Тьюринга