МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

Государственное образовательное учреждение

высшего профессионального образования

ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет автоматики и вычислительной техники

Кафедра электронных вычислительных машин

МАШИНА ТЬЮРИНГА

Отчет

Лабораторная работа №1

по дисциплине «Математическая логика»

Выполнил студент группы ВМ-22 _____________/Торощин А.С./

Проверил преподаватель _______________/Исупов К.С./

Киров 2011

Постановка задачи

Построить машину Тьюринга, реализующую заданный алгоритм: даны две матрицы 4х4, заполненные от 0 до 4. Получить третью путем сложения элементов.

Выполнение задачи можно разбить на два этапа:

1) Занесение символов из первой матрицы в третью

2) Занесение символов из второй матрицы в третью

Начальная конфигурация лент

1-ая лента (1-ая строка 1-ой матрицы)

Н

1

0

0

1

*

1

1

1

0

*

0

0

0

1

*

1

0

1

0

*

К

2-ая лента (2-ая строка 1-ой матрицы)

Н

1

0

0

1

*

1

1

1

0

*

0

1

1

0

*

0

1

0

1

*

К

3-ая лента (3-ая строка 1-ой матрицы)

Н

1

0

1

0

*

0

1

1

1

*

1

1

0

0

*

1

0

0

1

*

К

4-ая лента (4-ая строка 1-ой матрицы)

Н

1

1

1

1

*

0

0

0

0

*

1

1

0

0

*

0

0

1

0

*

К

5-ая лента (1-ая строка 2-ой матрицы)

Н

1

1

1

0

*

0

0

0

1

*

1

1

1

0

*

0

0

0

1

*

К

6-ая лента (2-ая строка 2-ой матрицы)

Н

1

1

1

0

*

1

1

0

1

*

1

0

0

1

*

1

1

0

1

*

К

7-ая лента (3-ая строка 2-ой матрицы)

Н

0

0

0

1

*

0

0

0

1

*

0

0

1

0

*

0

0

1

1

*

К

8-ая лента (4-ая строка 2-ой матрицы)

Н

1

1

1

1

*

1

1

1

0

*

1

1

0

1

*

0

0

0

0

*

К

9-ая лента (1-ая строка 3-ой матрицы)

Н

*

*

*

*

К

10-ая лента (2-ая строка 3-ой матрицы)

Н

*

*

*

*

К

11-ая лента (3-ая строка 3-ой матрицы)

Н

*

*

*

*

К

12-ая лента (4-ая строка 3-ой матрицы)

Н

*

*

*

*

К