TA1

в программе на Паскале:
х:= 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("зациклится");

отображение 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. Следующие множества являются эффективно счетными:

включает четыре типа команд Z(n), S(n), T(m, n),
J(m, n, q), где

Определим взаимно однозначное отображение

β (Z (n) ) = 4 × (n - 1);
β (S (n) ) = 4 × (n - 1) + 1;

программа для МНР.

Определим взаимно однозначное отображение

Определение 5. Пусть f – n-местная функция, вычислимая по программе P с геделевым номером m = γ (P). Число m будем называть индексом функции f. Вычислимую функцию от n переменных с индексом m будем обозначать символом

Каждая n-местная вычислимая функция f представлена в перечислении

Pr1 приводит к решению другой проблемы Pr2. В этом случае говорят, что проблема Pr2 сводится к проблеме Pr1. Таким образом, если проблема Pr2 сводится к проблеме Pr1, то из разрешимости Pr1 следует разрешимость Pr2 и, наоборот, из неразрешимости Pr2 следует неразрешимость Pr1.

проблемы в форме: «Остановится ли МНР, работая по программе с начальной конфигурацией (x)?». Другими словами: «Применима ли программа к своему кодовому номеру?».
Теорему 9 часто интерпретируют как утверждение о неразрешимости проблемы остановки, в которой говорится, что не существует общего метода, устанавливающего, остановится ли некоторая конкретная программа, запущенная с некоторым конкретным набором начальных данных.
Смысл этого утверждения для теоретического программирования очевиден: не существует общего метода проверки программ на наличие в них бесконечных циклов.