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

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

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

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

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

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

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

Отчет

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

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

Выполнил студент группы Ивт-11 _____________/Опарин А.Э./

Проверил преподаватель _______________/Чистяков Г.А./

Киров 2012

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

Построить машину Тьюринга, реализующую заданный алгоритм: дана матрица 5 на 5, нужно по столбцам преобразовать в 10СС, найти наибольшее число, и посчитать количество единиц в этом числе.

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

1. Занесение элементов из столбцов матрицы на ленту.

2. Перевод в 10 систему счисления .

3. Нахождение максимального числа.

4. Подсчёт количества единиц в максимальном числе.

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

1,2,3,4,5-ая лента (Запись матрицы по столбцам).

1	2	3	4	5
Н	Н	Н	Н	Н
Х	Х	Х	Х	Х
Х	Х	Х	Х	Х
Х	Х	Х	Х	Х
Х	Х	Х	Х	Х
Х	Х	Х	Х	Х
К	К	К	К	К

6-ая лента (Запись матрицы на ленте)

Н

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

K

7-ая лента (Перевод по столбцам в 10СС)

Н

X

X

X

X

X

K

8-ая лента (Кодирование)

Н

X

X

X

X

X

K

9-ая лента (Сортировка по возрастанию)

Н

Х

Х

Х

Х

Х

К

10-ая лента (Максимальное число)

Н

Х

Х

Х

Х

Х

К

11-ая лента (Число единиц в максимальном числе)

Н

Х

Х

Х

Х

Х

К