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

2. Изучалось обширное множество конкретных функций, интуи­ тивно алгоритмических. Все они оказались частично рекурсивными функциями, т.е. были найдены наборы инструкций для них в какой- нибудь стандартной формализации (нормальные алгоритмы или Тьюринговская схема), 3, Доказательство указанных результатов обладает следующей общей структурой. В каждом случае тот факт, что один формализо­ ванный класс функций содержится в другом, доказывается предъявле­ нием и обоснованием однообразной процедуры, согласно которой для любого набора инструкций J одной формализации указывается набор инструкции J ' другой формализации, приводящей к той же функции. Эта единообразная процедура оказывается в каждом случае алго­ ритмической (в неформальном смысле этого слова). Если действовать небудешь, никчемумапалата. Ш. Руставели § 19. Вопросы и темы для самопроверки 1. Интуитивное понятие алгоритма, его свойства. 2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные в данном алфавите алгоритмы, 3. Нормальный алгоритм (алгоритм А. А. Маркова), задание, примеры, 4. Функции вычислимые и частично-вычислимые по Маркову. 5. Замыкание, распространение нормального алгоритма. 6. Операции над нормальными алгоритмами; композиция, со­ единение, разветвление, повторение. 7. Машина Тьюринга, общее описание. 8. Задание машины Тьюринга, примеры. 9. Алгоритм Тьюринга, Вычислимость по Тьюрингу. 264