Положения машины Тьюринга. Алгоритмически неразрешимые проблемы: "остановка", эквивалентность алгоритмов, тотальность. Свойства алгоритма: дискретность, детерминированность, результативность, массовость. Выбор структуры данных. Решение на языке Haskell.
Аннотация к работе
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга. Целью данной курсовой работы является создание программы, реализующей машину Тьюринга на функциональном языке программирования Haskell. Чтобы достичь поставленной цели, необходимо решить следующие задачи: изучить принципы работы машины Тьюринга, её устройство, рассмотреть алгоритмически неразрешимые проблемы, выбрать структуру данных, описать реализуемые функции, а также привести примеры работы программы. 1. Основные положения машины Тьюринга Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины.