Категория
Информатика
Тип
реферат
Страницы
16 стр.
Дата
19.03.2014
Формат файла
.html — Html-документ
Архив
1008295.zip — 10.05 kb
  • mashina-tjuringa_1008295_1.html — 39.35 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы



Содержание

Введение. 2

1. Описание машины Тьюринга. 3

1.1 Свойства машины Тьюринга как алгоритма. 5

2. Сложность алгоритмов. 7

2.1 Сложность проблем… 9

3. Машина Тьюринга и алгоритмически неразрешимые проблемы… 12

Заключение. 16

Список литературы… 18


Введение

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

Устройство машины Тьюрингачрезвычайно просто, однако на ней можно выполнить практически любую программу. Длявыполнения всех этих действий предусмотрена специальная таблица правил, вкоторой прописано, что нужно делать при различных комбинациях текущих состоянийи символов, прочитанных с ленты.

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


1. Описание машины Тьюринга

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



Ваше мнение



CAPTCHA