Математическая логика и теория алгоритмов

Это означает, что применение алгоритма Тьюринга 7;^ к слову {К^,К2,...,К„) даст слово, означающее с точностью до слов SQ И SQ значение функции т.е. существует машина Тьюринга, вычисляющая эту функцию для любых значений ее аргументов. Пример. Рассмотрим всюду определенную функцию сложения f { x , y ) = x + y . Покажем, что эта функция вычислима по Тьюрингу. Для этого построим машину Тьюринга: до ^ S Q qo qo So R q\ q\ \ Rq\ • q\ * 1 qi qil Rqi qi SqLqi qi 1 So qi Нетрудно убедиться, что эта машина переводит слово 1...1 * 1 1...1 в слово ] а последнее слово означает т+1 н+1 ' т+н+1 ' число т+п, с.педовательно, эта машина Тьюринга вычисляет функцию х+у. Итак, функция х + у вычислима по Тьюрингу. Изразнообразия возникает совершенная гармония. Гераклит § 10. Связь между машинами Тьюринга и нормальными алгоритмами Теорелш 6.5. Пусть Т - машина Тьюринга с алфавитом А. Тогда существует нормальный алгоритм Б над 'А, вполне эквива­ лентный относительной алгоритму Тьюринга Л г,А. 239