Конспекты лекций по математической логике
    
    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 Машина Тьюринга - Поста.
    Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:
    Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).
    Допустимые команды:
    1) ,где .
    2) (остановка программы). Последовательность команд называется программой, если в этой последовательности не встречается команд с одинаковыми левыми частями. Машина останавливается если она не находит команды с левой частью подобной текущей.
    1.1.3 Нормальные алгоритмы Маркова.
    Тип машины перерабатывающий слова, в которой существует некий алфавит , для которого W - множество всех слов.
    Допустимые команды: (Для машин этого типа важна последовательность команд.)
    где Пример:
    Программа:
    
    1.1.4 Реализация функции натурального переменного.
    но мы допускаем не всюду определенную функцию.
    то это означает, что
    притом , если f не определена, то и программа не должна ничего выдавать.
    
    притом , если f не определена, то и программа не должна ничего выдавать.
    ( , а числа представляются в виде ,например .)
    1.2 Эквивалентность трех подходов к понятию алгоритм.
    1.2.1 Теорема об эквивалентности понятия вычислимой функции.
    вычислима: ()
    1) Если существует программа МНР, которая вычисляет эту функцию.
    2) Если существует программа МТ-П, которая вычисляет эту функцию.
    3) Если существует программа НАМ, которая вычисляет эту функцию.
    
    Использование НАМ:
    
    
    Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.
    Пусть которая вычисляется на МТ-П, вычислим её на НАМ.
    МТ-П:
    
    НАМ:
    Команда МТП: преобразуется по правилам:
    
    Команда МТП:
    
    2. ............