| 0 | 1 | 1 | 0 | 0 |
|
|
|
|
| |
| 0 | 1 | 1 | 1 | 0 | Вектор Брадобрея – D | |||||
|
|
|
|
|
| ||||||
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | 1 | ||||||
|
|
|
|
|
| ||||||
| 1 | 1 | 1 | 0 | 1 |
|
|
|
|
| |
Правило "Брадобрей бреет тех и только тех жителей деревни, которые не бреются сами":
i D[i] Т [i, i] (*)
В нумерации жителей деревни Брадобрей имеет номер. Если его номер i, то по правилу построения таблицы Т, массив D должен был бы целиком совпадать со строкой номер i таблицы Т, то есть
j D[j] = T[i, j]
При j равном i D[i] = Т [i, i] – противоречие с требованием (*).
Из требования (*) следует, что строка D не может совпадать ни с одной из строк таблицы Т.
Проблема зацикливания в в МНР и стандартном программировании.
Примером "бесконечного цикла" в программе на Паскале:
х:= 1; repeat
{ какие-то действия, которые не изменяют значение переменной x. }; until x>10;
if z=0 then
writeln("He зациклится") (A) else
writein("зациклится");
if z=0 then
repeat until false (B) else
writein("зациклится");
Определение 1. Множество X называют счетным, если можно установить взаимно однозначное отображение f : Z0 X между множеством неотрицательных
целых чисел Z0 и множеством X.
Определение 2. Множество называют не более чем счетным, если оно счетно или конечно.
Определение 3. Перечислением или нумерацией множества X называется отображение f : Z0 X множества Z0 на множество X.
Перечисление f определяет на множестве X некоторую бесконечную последовательность x0, x1, x2 … (xi = f ( i ).
Если отображение f - взаимно однозначно, то f называют перечислением или нумерацией
без повторений.
Определение 4. Множество X называется эффективно счетным, если существует функция f : Z0 X , устанавливающая взаимно однозначное соответствие между
множествами Z0 и X такая, что f и f -1 - вычислимые функции. Теорема 1. Следующие множества являются эффективно счетными:
| a) | Z0 Z0 |
| b) | Z0 Z0 Z0 |
c) Z 0k
k 0
| Y |
|
|
|
|
| ( 0 , 5 ) | ( 1 , 5 ) | ( 2 , 5 ) | ( 3 , 5 ) | ( 4 , 5 ) |
| ( 0 , 4 ) | ( 1 , 4 ) | ( 2 , 4 ) | ( 3 , 4 ) | ( 4 , 4 ) |
| ( 0 , 3 ) | ( 1 | , 3 ) | ( 2 , 3 ) | ( 3 , 3 ) | ( 4 , 3 ) | |
|
|
| 7 | 6 |
|
| |
| ( 0 | , 2 ) | ( 1 | , 2 ) | ( 2 , 2 ) | ( 3 , 2 ) | ( 4 , 2 ) |
| 3 |
|
| 2 | 5 |
|
|
| ( 0 | , 1 ) | ( 1 | , 1 ) | ( 2 , 1 ) | ( 3 , 1 ) | ( 4 , 1 ) |
| 0 | 1 | 4 |
|
| ||
| ( 0 | , 0 ) | ( 1 , 0 ) | ( 2 , 0 ) | ( 3 , 0 ) | ( 4 , 0 ) | |
( 5 , 5 )
( 5 , 4 )
( 5 , 3 )
( 5 , 2 )
( 5 , 1 )
| ( 5 , 0 ) | X |
(a1, a2 , ..., ak ) 2a1 2a1 a2 1 2a1 a2 a3 2 ... 2a1 a2 ... ak (k 1) 1
| (a , a | 2 | , ..., a | k | ) 10...01...10...010...0 1 | ||
| 1 |
|
|
|
| ||
| Однозначность: |
| ak | a2 | a1 | ||
|
|
|
|
| |||
(a1, a2 , ..., ak ) (b1, b2 , ..., bm ) (a1, a2 , ..., ak ) (b1, b2 , ..., bm )
| 1(x) 1((x 1) | 2 | 1) | 1(10...01...10...010...0 1) | (a , a | 2 | , ..., a | k | ) | |||
|
|
|
|
|
|
| 1 |
|
| |||
|
|
|
|
| ak | a2 | a1 |
|
|
|
|
|
| Теорема 2. Множество K команд МНР эффективно счетно. |
|
|
|
|
| ||||||
| Множество K команд МНР включает четыре типа команд Z(n), S(n), T(m, n), |
|
| |||||||||
| J(m, n, q), где m, n, q N. |
|
| : K Z0 |
|
|
|
| ||||
| Определим взаимно однозначное отображение |
|
|
|
| |||||||
(Z (n) ) = 4 (n - 1);
(S (n) ) = 4 (n - 1) + 1;
(T (m, n)) 4 2 (m 1, n 1) 2
(J (m, n, q)) 4 3 (m 1, n 1, q 1) 3
Теорема 3. Множество P всех программ для МНР эффективно счетно.
P (I1, I2 , ..., Is ) - произвольная программа для МНР. Определим взаимно однозначное отображение : P Z0
(P) (I1, I2 , ..., Is ) ( (I1 ), (I2 ), ..., (Is ))
Определение 5. Пусть f – n-местная функция, вычислимая по программе P
с геделевым номером m = (P). Число m будем называть индексом функции f. Вычислимую функцию от n переменных с индексом m будем обозначать символом
Каждая n-местная вычислимая функция f представлена в перечислении
f0n , f1n , f2n , ...
Нет комментариевНе стесняйтесь поделиться с нами вашим ценным мнением.
Текст