Читать онлайн «Теория алгоритмов. Предикаты»

ТишинВ. В. Теория алгоритмов, предикаты. Пособие содержит краткую теорию и варианты заданий по теории алгоритмов, включающих разделы, связанные с машинами Тьюринга, нормальными алгоритмами Маркова, а также теории рекурсивных функций. Рассматриваются также вопросы, связанные с теорией предикатов. Пособие рекомендовано к изданию кафедрой Прикладной математики Самарского государственного аэрокосмического университета. Оглавление Теория алгоритмов Машины Тьюринга 3 Нормальные алгоритмы 17 Рекурсивные функции 25 Предикаты 31 Список литературы ... . . 43 Компьютерная вёрстка и оригинал-макет автора. ©ВВ. Тишин,2002 Теория алгоритмов Глава 1. Машины Тьюринга. Машиной Тьюринга называется пятёрка объектов Т = ( A, S, 5, v, ц ) , где А = { а|5 а2,... , ап } - алфавит; 5 = { s0, s ,... ,sm } - множество внутренних состояний, причём s0 - заключительное, a s{ - начальное состояния. 6 : S х А -> S - функция перехода; v : S х А -> А - функция выхода; ц : S х А -> { П, Л, Н}- функция управления. Командой машины Тьюринга называется запись вида akst -> apD Sj, где ар, D, Sj - значения на наборе aks; функций 5, ц,у соответственно. Программой машины Тьюринга называется набор всех её команд. Работа машины Тьюринга связана с бесконечной лентой, разбитой на ячейки, причём в каждой ячейке может быть записан один символ некоторого алфавита, причём X является символом пустой ячейки. Работа машины Тьюринга над словом а, записанным на ленте, проходит следующим образом: машина Тьюринга начинает свою работу всегда в состоянии Sj, а её считывающее устройство расположено над первым слева символом слова, записанного на ленте; считав символ в ячейке, обозреваемой считывающим устройством машины Тьюринга, она печатает' в эту ячейку символ, найденный с помощью функции выхода v, двигается вдоль ленты вправо, влево или остаётся на месте, в случае, если функция ц принимает значения П, Л, или Н соответственно и переходит в состояние, определяемое с помощью функции перехода 5; при переходе машины Тьюринга в состояние s0 считают, что она закончила работу над словом а и говорят, что машина Тьюринга применима к слову а. 3 Глава 1 Если машина Тьюринга при работе над словом а не переходит в состояние s0, то говорят, что она не применима к слову а. Конфигурацией машины Тьюринга называется запись а,Ьа2, где b - символ ячейки, обозреваемой считывающим устройством машины Тьюринга, находящейся в состоянии sk, aa,Ha2- слова, записанные на ленте соответственно левее и правее символа Ь. Кодом машины Тьюринга называется запись набора её команд в алфавите {*ЛЬ позволяющая однозначно восстанавливать каждую команд}'. Машина Тьюринга называется самоприменимой (несамоприме- нимой), в случае, ели она применима (не применима) к своему коду. Числовой функцией называется функция вида f: N0k ^N0, keN. Изображением набора аргументов (х^х^... ^) называется запись вида Г1+!хГ:+!ХГ,+1... ?и1ч+!? гДе 1г=ЦЛ- граз Числовая функция f(x jX^... ^) называется вычислимой по Тьюрингу^ если существует машина Тьюринга, применимая к любому слову вида (*),переводящая его в слово ly+l, где у = f^x^,... ^).