Теория алгоритмов. Зюзысов В.М. - 11 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

рекурсивная функция |x–y
2
|, мы обнаруживаем, что g(x) = µy[f(x,y)=0] – не всюду
определенная функция:
g(x) =
x , если x есть точный квадрат, и неопределенна в противном случае.
Таким образом, тривиально используя µ-оператор вместе с суперпозицией и
рекурсией, можно построить больше функций, исходя из основных, чем только с
помощью суперпозиции и рекурсии (так как эти операции порождают из всюду
определенных функций – всюду определенные). Существуют, однако, и общерекурсивные
(всюду определенные) функции, для построения которых нельзя обойтись без
минимизации.
Приведем пример функции, не являющейся примитивно рекурсивной, хотя и
вычислимой в интуитивном смысле.
Определим последовательность одноместных функций F
n
: N→ N, n∈N,
следующим образом:
F
0
(x) = x+1,
F
n+1
(x) = F
n
(F
n
(…F
n
(1)…))
x+1 раз
Поэтому F
1
(x) = x+2, F
2
(x) = 2x+3 ≈ 2x, F
3
(x) ≈ 2
x
,
F
4
(x) ≈ (башня из x+1 двойки) и т. д.
2
.
.
.
2
2
Имеем следующие свойства:
1) для каждого n функция x→ F
n
(x) является примитивно-рекурсивной;
2) F
n
(x) > 0,
3) F
n
(x+1) > F
n
(x),
4) F
n
(x) > x,
5) F
n+1
(x) ≥ F
n
(x+1),
6) для каждой k–местной примитивно-рекурсивной функции .f(x
1
,x
2
,…,x
k
) существует
такое n, что F
n
мажорирует f, т.е. f(x
1
,x
2
,…,x
k
) ≤ F
n
(max(x
1
,x
2
,…,x
k
)) для всех
x
1
,x
2
,…,x
k
,
7) функция A(n, x) = F
n
(x) не является примитивно-рекурсивной [11, с. 53] (эта
функция известна как функция Аккермана).
Функцию Аккермана можно определить и в традиционной записи:
f(0, y) = y+1,
f(x+1,0) = f(x,1),
f(x+1,y+1) = f(x, f(x+1,y)).
Позднее мы приведем доводы в пользу правдоподобности того, что понятие
частично-рекурсивной функции есть точный
математический эквивалент интуитивной
идеи (эффективно) вычислимой функции.
1.3 Машины Тьюринга
Рассмотрим еще один способ определения вычислимых функций, следуя в
изложении [24, с. 12–14]. Формулировка, выраженная в терминах воображаемой
вычислительной машины, была дана английским математиком Аланом Тьюрингом в 1936
г. Главная трудность при нахождении этого определения была в том, что Тьюринг искал
его до создания реальных цифровых вычислительных машин. Познание шло от

Страницы