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

Сти

раем палочку.

Дви

жемся до пер

вой

циф

ры и увели

чива

ем ее на единицу

q_3l

Lq_er H

Lq_d Л

1q_er H

2q_er H

3q_er H

4q_er H

5q_er H

6q_er H

7q_er H

8q_r H

9q_3l Л

0q_2l Л

q_d

1q_r H |q_d Л 2q_r H 3q_r H 4q_r H 5q_r H 6q_r H 7q_r H 8q_r H 9q_r H 0q_r Л 1q_r Л

Рис.4. Машина Тьюринга для U((n)₁ )=(n)₁₀

Оценим сложность этого алгоритма. В начале работы каретка пройдет (n-1) символ при движении влево и (n-1) символ при движении обратно, т.е. 2(n-1). На втором проходе - 2(n-2) и т.д. Отсюда число пройденных палочек, а следовательно и выполненных команд будет равно n(n-1). Машина n раз выполнит команду, увеличения текущей цифры на 1. Количество просмотров цифр будет равно ([log₁₀ n]+1)([log₁₀ n]).Таким образом, получаем

n(n-1)+n+[log₁₀ n]× ([log₁₀ n]+1) @ n² +[log₁₀ n(log₁₀ n+1)]

Пример 4. Построить машину Тьюринга, для сравнения двух чисел a и b, заданных в унарной форме.

если

Пусть на ленте числа a и b заданы в унарной форме. Каретка располагается над лентой так, как показано на рисунке 5,