Категория
Информатика
Тип
контрольная работа
Страницы
2 стр.
Дата
07.09.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
124665.zip — 22.4 kb
  • mashina-tjuringa_124665_1.rtf — 203.39 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Машина Тьюринга Проничевы Diapsalmata
5
Содержание
Введение 2
1. Описание машины Тьюринг а 3
1.1 Свойства машины Тьюринга как алгоритма
5
2. Сложность алгоритмов
7
2.1 Сложность проблем
9
3. Машина Тьюринга и алгоритмически неразрешимые проблемы
12
Заключение 16
Список
литературы
18
Введение
Машина Тьюринга -
это очень простое вычислительное устройство . Она состоит из ленты бесконечной длины , разделенной на ячейки
, и головки , которая перемещается вдоль
ленты и способна читать и записывать символы . Также у машины Тьюринга есть такая характеристика , как состояние , которое может выражаться целым числом
от нуля до некоторой максимальной величины
. В зависимости от состояния машина Тьюринга может выполнить одно из трех действий : записать символ в ячейку , передвинуться на
одну ячейку вправо или влево и установить
внутреннее состояние .
Устройство машины Тьюринга чрезвычайно просто , однако на ней можно выполнить практически люб ую программу .
Для выполнения всех этих действий предусмотрена специальная таблица правил , в которой прописано , что нужно делать при различных комбинациях текущих состояний и символов
, прочитанных с ленты .
В 1947 г . Алан Тьюринг
расширил определение , описа в " универсальную машину Тьюринга
". Позже для решения определенных классов задач была введена ее
разновидность , которая позволяла выполнять не
одну задачу , а несколько .
1 . Описание
м ашин ы Тьюринга
Алан Тьюринг (Turing )
в 1936 г оду опубликовал в трудах Лондонского математического общества статью
" О вычислимых



Ваше мнение



CAPTCHA