Конспекты лекций по математической логике.

1. Теория алгоритмов
1.1 Различные подходы к определению алгоритма:

10. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).

20. Машина с неограниченными регистрами (МНР).

30 Машина Тьюринга – Поста (МТ-П).

40 Нормальные алгоритмы Маркова (НАМ).

1.1.1 Машина с неограниченными регистрами (МНР).

Имеется некое устройство, в котором счетное число ячеек памяти

(регистров), в которых хранятся целые числа.
Допустимые команды:

Z(n) - обнуление регистра Rn.

S(n) - увеличение числа в регистре Rn на 1.

T(m,n) - копирует содержимое Rm в регистор Rn.

I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет следующая.
Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.

Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.

1.1.2 Машина Тьюринга - Поста.
Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: [pic] , где [pic] - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии [pic]. Также существуют внутренние состояния машины: [pic]
Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).
Допустимые команды:
|1) [pic] ,где [pic]. |Последовательность команд |
|2) [pic] (остановка программы). |называется программой, если в этой|
| |последовательности не встречается |
| |команд с одинаковыми левыми |
| |частями. Машина останавливается |
| |если она не находит команды с |
| |левой частью подобной текущей. |

1.1.3 Нормальные алгоритмы Маркова.
Тип машины перерабатывающий слова, в которой существует некий алфавит
[pic], для которого W - множество всех слов.
Допустимые команды: (Для машин этого типа важна последовательность команд.)
|[pic] где [pic] |Пример: [pic] [pic] |
| |Программа: [pic] |
| |[pic] |

1.1.4 Реализация функции натурального переменного. [pic]
[pic] но мы допускаем не всюду определенную функцию.
[pic] то это означает, что [pic] притом [pic], если f не определена, то и программа не должна ничего выдавать.
[pic] [pic][pic][pic] притом [pic], если f не определена, то и программа не должна ничего выдавать.
([pic] , а числа представляются в виде [pic] ,например [pic] .)
1.2 Эквивалентность трех подходов к понятию алгоритм.

1.2.1 Теорема об эквивалентности понятия вычислимой функции.
[pic] вычислима: ([pic])
1) Если существует программа МНР, которая вычисляет эту функцию.
2) Если существует программа МТ-П, которая вычисляет эту функцию.
3) Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ: [pic] [pic]
[pic] [pic]

Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

Пусть [pic] которая вычисляется на МТ-П, вычислим её на НАМ.

МТ-П: [pic]

НАМ: [pic]

Команда МТП: [pic] преобразуется по правилам:
[pic]
Команда МТП: [pic] [pic] [pic]

2. Булевы функции.
2.1 Основные определения
2.1.1 Декартово произведение
[pic] - мн-во всевозможных упорядоченных пар элементов из А и В.
Пример: [pic]
[pic] [pic]
[pic]