Билет №32. Алгоритмическая система э. Поста.

v

v

v

Алгоритмическая система Поста, или машина Поста представляет собой следующую конструкцию: - имеется бесконечной1 длины магнитная лента - на магнитной ленте можно выполнять следующие операции: 1) записать метку v 2) стереть метку Состояние задается: - содержанием ячеек магнитной ленты - начальным положением каретки - программой для машины Поста Команды: 1) – обозначает движение каретки вправо и переход к следующей операции j 2) – обозначает движение каретки влево и переход к следующей операции j 3) i.Vj – обозначает запись метки и переход к следующей операции j 4) – обозначает стирание метки и переход к следующей операции j 5) i.?j1,j2 – команда передачи управления 6) стоп I - номер команды, j – номер следующей команды, которая будет выполняться Если встречается команда вписать метку в ячейску с меткой или стирать пустую ячейку, то программа произведет безрезультатную остановку. Пример. Составить программу на машине Поста, которая вычисляет число меток n+1. 1.=>2 2.?3,1 (здесь переход к команде 3 если нет метки, к команде 1 если метка есть в данной ячейке) 3.V4 4.стоп Иллюстрация к примеру в самом начале билета.

Билет №33. Алгоритмическая система а. Тьюринга (1937 год)

L

P

1) Б

Q

есконечная лента, в которой хранятся исходные данные решаемой задачи 2) L-логический блок машины Тьюринга 3) Внешний алфавит – набор символов, которые записываются на магнитную ленту 4) В каждой ячейке храниться только один символ Внутренний алфавит машины: 1) Команды: -влево -вправо -стояние на месте q1,q2,q3,… - внутренние состояния логического блока Обработка данных происходит в L Данный блок имеет 2 входных канала: - символ с обозреваемой ячейки - состояние машины Имеет 3 выхода: - преобразованный символ - команда перемещения головки - переход на новое состояние Пример. На ленту записывается число n. На ленту нужно записать результат n+1 Внутренний алфавит: q0,q1,!,Л,П,Н, v-пустой символ

0	1!
1	2!
2	3!
3	4!
4	5!
5	6!
6	7!
7	8!
8	9!
9	0Л
v	1I
I	1!	vПq0

Пример. Сложение двух чисел.

I

I

I

I

I

*

I

I

I

I

Программа на машине Тьюринга

	Q0	Q1	Q2
I	VПQ0	Л	П
V	П	ПQ0	ПQ1
*	V!	Л	П

Билет №34. Ассоциативные исчисления и проблема эквивалентности слов. Пусть имеется какое либо слово R, состоящая из A={a,b,c}, например abbc и имеется группа подстановок. Тогда встает вопрос о том, возможно ли перейти от слова R к слову R1 используя эту группу подстановок? Существует ли дедуктивная цепочка по переходу из одного слова в другое? Ответ на этот вопрос и является основной проблемой эквивалентности слов. Марков сумел сформулировать ответ на эту проблему, создав нормальный алгоритм по переходу из одного слова в эквивалентное ему.

Б илет №35. Алгоритмическая система Маркова. Пусть имеется следующее множество: A={a,b,c,….} и существует система подстановок p1=>q1 p2=>q2 ……….. pn=>qn Пусть есть слово R, которое можно преобразовать в слово S с помощью подстановок. Алгоритм Маркова применяется только в том случае, если процесс переработки R конечен. Пример. A={a,b,c} 1)cb=>cc 2)cca=>ab 3)ab=>bca 4)ca=>L R=cabc=>cccac=>cabc В алгоритме Маркова порядок подстановок имеет огромное значение. Данное обозначение значит, что подстановка используется один раз.

Билет №36. Сравнительный анализ алгоритмических систем и транслируемость абстрактных программ. При ответе на данный вопрос необходимо рассказать про алгоритмические системы Маркова, Тьюринга, Поста. Необходимо сказать что есть следующая гипотеза: Все алгоритмические системы можно записать виде машины Тьюринга. То есть все алгоритмические системы эквивалентны, включая ассоциативные исчисления.

Билет №37. Понятие рекурсивных функций. Вычислимая функция – функция для которой существует алгоритм для ее вычисления. Рекурсивные функции состоят из примитивных функций следующего типа: 1) f(x)=x+1 2) 0(x)=0 3) Imn(x1,x2,…,xn)=Xm , где m меньше n. (оператор проектирования, селекторная функция) Примеры: f(0(x))=f(0)+1-0+1=1 f(f(0(x)))=1+1=2 Термин рекурсивная функция используется для обозначения трех классов функций: -примитивно-рекурсивные функции -общерекурсивные функции -частично-рекурсивные функции Примеры приведенные выше отражают примитивно-рекурсивные функции Частично-рекурсивная функция определяется аналогично примитивно-рекурсивной функции, только добавляется еще один оператор минимизации. Оператор минимизации аргумента: Пусть f – функция от n натуральных переменных. Тогда результатом приминения оператора минимума к аргументу функции f называется функция h от n-1 переменной, задаваемая следующим определением: h(x1,…,xn-1)=min(y), при условии, что f(x1,…,xn-1,y)=0 Пример. h=0 Общерекурсивная функция - частично-рекурсивная функция, определенная для всех значений аргументов. Тезис Черча. Класс алгебраически вычислимых функций совпадает с классом всех частично-рекурсивных функций.