Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Упражнение. 3.1. Покажите, что вычисление по алгоритму из примера 6 с начальной конфигурацией 6, 7, 0, 0, 0,



3.1. Покажите, что вычисление по алгоритму из примера 6 с начальной конфигурацией 6, 7, 0, 0, 0,... никогда не остановится.

Для удобства обозначим через P (a1, a2,..., an) вычисление по алгоритму P с начальной конфигурацией a1, a2,..., an, 0, 0,.... Если вычислительный процесс заканчивается с результатом b, будем писать P (a1, a2,..., an) = b.

Определение 3.1. Пусть f - функция от n неотрицательных целыхпеременных со значениями во множестве Z0 неотрицательных целых чисел(функция ). Функция f называется вычислимой на МНР (или МНР–вычислимой), если существует такой алгоритм P, что

1) вычисление P (a1, a2,..., an) останавливается тогда и только тогда, когда (a1, a2,..., an) принадлежит области определения f;

2) если (a1, a2,..., an) принадлежит области определения f; то в заключительной конфигурации в регистре R1 находится целое число b такое, что f (a1, a2,..., an) = b.

С этого момента под термином вычислимое будем подразумевать МНР–вычислимое.

Рассмотрим теперь несколько простых примеров вычислимых функций.

Пример 3.2. Докажите МНР-вычислимость функции x + y.

Решение. Получим x + y, прибавляя y раз 1 к числу x. Начальной конфигурацией алгоритма служит x, y, 0, 0, 0,.... Типичной конфигурацией в процессе вычисления является

R1 R2 R3 R4 R5 ...
x + k y k 0 0 ...

Определим алгоритм следующим образом:

I1 J(3, 2, 5)
I2 S(1)
I3 S(3)
I4 J(1, 1, 1)

Заданный алгоритм вычисляет функцию x + y.

Пример 3.3. Докажите МНР-вычислимость функции

Решение. Составим алгоритм для начальной конфигурации x, 0, 0,.... Типичной конфигурацией в процессе вычисления является:

R1 R2 R3 R4 R5 ...
x k k + 1 0 0 ...

Следующий алгоритм МНР-вычисляет функцию.





Дата публикования: 2015-03-26; Прочитано: 376 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...