Главная
Проблема исчисления предикатов
Процедура унификации
Отношения на функциях принадлежности
Неразрешимые алгоритмические проблемы МТ
Полнота и непротиворечивость
NP-полные (универсальные) задачи
Стандартизация услуг
Стандартизация и экология
Организационные и методические принципы сертификации в России
Программа сертификации
Метрологический надзор
Структура кристаллов
Судьбы крестьянские
Еще одна фальшивая ценность
Такая судьба
Соприкосновение с рынком
Мой театр, мои коллеги
Гастроли
И жизнь и слезы и любовь
Возвращение из Томска
Реклама:
|
|
Отношения на функциях принадлежности
правильно вычислимой по Тьюрингу. Таким образом, алгоритм отождествляется вычислимой функции. То есть отображению входных данных в выходные.
Примеры машин Т. Приведем примеры элементарных вычислимых функций, реализовав их на МТ. Эти алгоритмы будут базовым набором аксиом формальной теории.
Данные, являющиеся числами, будем записывать в унарном коде, то есть, если a=5, то на ленте a – 11111(a-раз), и кратко обозначается 1a.
Тогда функция сложения натуральных чисел, будет вычислима на МТ Т+, описание ее приведено ниже.
Для начала отметим, что a+b=1a+1b=1a+b
Тогда сложение двух чисел, записанных на ленте через разделитель *, осуществляется стиранием разделителя и сдвигом второго числа к первому.
Итак, Т+ будет
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
