Тема 5. Машины Тьюринга

План лекции:

1. Общие сведения

2. Неформальное определение машины Тьюринга

3. Формальное определение машины Тьюринга

1. Общие сведения

Одним из первых формальных определений алгоритма было определение английского математика А. Тьюринга, который в 1936 г. описал схему некоторой гипотетической (абстрактной) машины и формализовал правила выполнения действий при помощи описания работы этой машины.

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

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

Дата добавления: 2015-07-26; просмотров: 164; Нарушение авторских прав

Мы поможем в написании ваших работ!