Нумерация черча

.

Проверим выполнение формы записи :

(33)Чистое исчисление

Чистое исчисление получается при удалении констант и правил, так как в нем любые константы и функции можно построить атомарными термами, использующие только лишь переменные.

ПРИМЕРЫ:

а) ;

б) ;

в) .

Легко проверить, что выполняются следующие редукции:

1.

2.

3.

Нумерация Черча: представлять композицией , т. е. , т. е. повторяется раз. Для каждого натурального положим: ,

. Тогда «сложение» чисел определяется выражением:

.

Проверка:

Определение: Говорят, что частичная функция с аргументами определима термом , когда терм редуцируется к терму , если значение определено, и не имеет нормальной формы, если не определено.

Теорема Клини: Частичная функция частично-рекурсивна тогда и только тогда, когда она определима.

(34) МАШИНЫ ТЬЮРИНГА (автор Алан Тьюринг) – 3-й способ определения вычислимых функций

Суть способа: лента с “0” и “1” поступает на вход «черного ящика» – ЭВМ. Черный ящик – ЭВМ – используется для входной ленты как пространство памяти ячеек для вычисления в виде инструкций для перехода из одного состояния в другое (модель конечного автомата).

Т. е., «машина Тьюринга» – функция перехода под действием входных данных из одного состояния в другое.

Один шаг действия может быть 3-х типов:

а) предыдущий символ ячейки ленты стирается, а пишется символ (может быть старый); б) лента сдвигается вправо (П) или влево (Л); в) указывается следующая инструкция (ее номер).

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

Например, пусть . То есть, когда машина дойдет до инструкции , а на обозреваемой ячейке написан символ 1, она его стирает, и оставляет 0. Ленту передвигает влево и переходит к инструкции . Если инструкция не определена, то, дойдя до инструкции , а на ячейке написан 1, то машина останавливается.

Входные данные и выходные данные – это строчки из 1, разделенные 0.

Пусть — строчка из 1 длины . Тогда строка, состоящая из строчек из 1, разделенными 0.

Определение 2: Пусть область определения местной функции . Функция называется «вычислимой», если существует машина Тьюринга такая, что как только начинает с инструкции , обозревая самый левый символ строки (вся остальная часть ленты пуста) тогда: