Вычислимые функции

Говорят, что машина Тьюринга вычисляет функцию f(x₁, x₂, ..., x_n), если выполняются следующие условия:

1) для любых x₁, x₂, ..., x_n, принадлежащих области определения функции, машина Тьюринга из начальной конфигурации, имея на ленте представление аргументов, переходит в заключительную конфигурацию, имея на ленте результат (представление функции);

2) для любых x₁, x₂, ..., x_n, не принадлежащих области определения функции, машина Тьюринга из начальной конфигурации работает бесконечно.

Если начальная и заключительная конфигурации машины Тьюринга являются стандартными, то говорят, что машина Тьюринга правильно вычисляет функцию f.

Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее.

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

Машины Тьюринга могут вычислять искомую функцию с восстановлением и без восстановления. Вычисление функции с восстановлением означает u1088 работу машины Тьюринга с сохранением исходных данных:

Приведенное определение позволяет получать на ленте сначала результат, а затем исходные данные. В отдельных случаях удобно сделать наоборот:

Вычисление функции без восстановления означает работу машины Тьюринга без сохранения исходных данных:

Справедливо утверждение, что всякая правильно вычислимая функция правильно вычислима с восстановлением.

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

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