Нумерация черча
.
Проверим выполнение формы записи :
(33)Чистое исчисление
Чистое исчисление получается при удалении констант и
правил, так как в нем любые константы и функции можно построить атомарными термами, использующие только лишь переменные.
ПРИМЕРЫ:
а) ;
б) ;
в) .
Легко проверить, что выполняются следующие редукции:
1.
2.
3.
Нумерация Черча: представлять композицией
, т. е.
, т. е.
повторяется
раз. Для каждого натурального
положим:
,
. Тогда «сложение» чисел определяется
выражением:
.
Проверка:
Определение: Говорят, что частичная функция с
аргументами
определима термом
, когда терм
редуцируется к терму
, если значение
определено, и
не имеет нормальной формы, если
не определено.
Теорема Клини: Частичная функция частично-рекурсивна тогда и только тогда, когда она определима.
(34) МАШИНЫ ТЬЮРИНГА (автор Алан Тьюринг) – 3-й способ определения вычислимых функций
Суть способа: лента с “0” и “1” поступает на вход «черного ящика» – ЭВМ. Черный ящик – ЭВМ – используется для входной ленты как пространство памяти ячеек для вычисления в виде инструкций для перехода из одного состояния в другое (модель конечного автомата).
Т. е., «машина Тьюринга» – функция перехода под действием входных данных из одного состояния в другое.
Один шаг действия может быть 3-х типов:
а) предыдущий символ ячейки ленты стирается, а пишется символ (может быть старый); б) лента сдвигается вправо (П) или влево (Л); в) указывается следующая инструкция (ее номер).
Определение 1: Машина Тьюринга – это функция такая, что для некоторого натурального числа
область определения этой функции есть подмножество множества
, а область значений есть подмножество множества
Например, пусть . То есть, когда машина дойдет до инструкции
, а на обозреваемой ячейке написан символ 1, она его стирает, и оставляет 0. Ленту передвигает влево и переходит к инструкции
. Если инструкция
не определена, то, дойдя до инструкции
, а на ячейке написан 1, то машина останавливается.
Входные данные и выходные данные – это строчки из 1, разделенные 0.
Пусть — строчка из 1 длины
. Тогда
строка, состоящая из
строчек из 1, разделенными 0.
Определение 2: Пусть область определения
местной функции
. Функция
называется «вычислимой», если существует машина Тьюринга
такая, что как только
начинает с инструкции
, обозревая самый левый символ строки
(вся остальная часть ленты пуста) тогда: