Реферат: Формализация понятия алгоритма

Рис.5.

т.е. над крайне правым символом | числа a . Cравнивать числа a и b будем, стирая попарно одну палочку в записи a и одну палочку в записи b. Если останутся палочки только в записи a, то значит a>b, если только в записи b, то a<b, а если палочек не останется вовсе, то a=b. На рисунке 6 показана программа для Машины Тьюринга, вычисляющей U₁ .

L	|	x	1	0
qo	Lqer H	xqr H	xqer H
qr	LqCHL Л	xql H	xqr П
ql	LqCHR П	xqr H	xql Л
qCHL	Lqa=b П	|qa>b H	xqCHL Л
qCHR	Lq’a=b Л	|qa<b H	xqCHR П
qa=b	1!H	|qer H	Lqa=b П
q’a=b	1!H	|qer H	Lq’a=b Л
qa>b	Lq’a>b Л	|qa>b П	xqa>b П
q’a>b	1!H	|qa>b Л	Lq’a>b Л
qa<b	Lqer H	|qa<b Л	0q’a<b Л
q’a<b	Lq’a<b П	|qer H	xq’a<b Л	1qer H	0!H

Рис.6.

Теперь уместно спросить, в чем же принципиальные отличия записи алгоритмов, в форме Машины Тьюринга от того, которое мы использовали в лекции 1?

Прежде всего в представленных данных. В алгоритме Евклида нахождения НОД мы говорили, что а и b представляют числа.

Что такое число? Какова форма его записи?

От ответов на эти вопросы будут зависеть правила действий над ними для вычисления разности, сравнения чисел и т.д. Поэтому сказать, что а и b - это числа не достаточно. Необходимы соответствующие уточнения, договоренности между исполнителями.

У Машины Тьюринга данные - это слова в некотором алфавите. Слово в алфавите - это конечная последовательность символов из определенного множества, называемого алфавит.

Второе принципиальное отличие - действия. При интуитивном рассмотрении понятия алгоритма мы использовали действия: положи, умножь, сложи, сравни и т. д., смысл которых мы считаем по умолчанию общеизвестным. Хотя, если предположить, что речь идет о числах в логарифмической системе счисления (см. Каут. “Искусство программирования”), то вряд ли можно считать, что смысл операции умножения является общеизвестным. В то же время, сравнить два символа: совпадают они или нет может каждый человек и заменить один символ на другой тоже.

Поэтому, запись алгоритма в терминах Машины Тьюринга более строгая, в том смысле, что она не имеет двусмысленностей, понимается однозначно. Отсюда и рассуждения о ее свойствах более четкие и строгие, чем в интуитивном смысле.

Однако, возникает другой вопрос. А любую вычислимую функцию можно описать в виде Машины Тьюринга? Ответ на этот вопрос Тьюринг сформулировал в виде тезиса, названного его именем.

Тезис Тьюринга: Для любой интуитивно вычислимой функции существует МТ, ее вычисляющая.

Это тезис, а не теорема. Его нельзя доказать, так как в нем используется понятие интуитивно вычислимой функции, смысл которого определен интуитивно, т.е. не строго.

Выводы :

А реализуют лишь подмножество (класс вычислимых функций) функции, рассматриваемых в курсе математического анализа;

Алгоритмизация решения задачи состоит в разбиении задачи на подзадачи, подзадач на подподзадачи и т.д., до тех пор, пока решение очередной подзадачи мы не сведем к действиям надлежащего исполнителя;

МТ можно строить из ранее построенных МТ.

Вопросы:

Квадратный корень из x - вычислимая функция?

Что такое вычислимая функция?

Как отличить вычислимую функцию от не вычислимой?

Множество вещественных чисел перечислимо?

Что такое перечислимое множество?

Мн-во четных целых чисел разрешимо относительно мн-ва целых чисел?

Сформулируйте условие разрешимости мн-ва В относительно мн-ва М.

Перечислить параметры для уточнения поняти А.

Как в МТ задаются исходные данные?

Как в МТ задаются возможные результаты?

Как в МТ задаются промежуточные результаты?

Как в МТ задается правило начала работы А?