7 Билет
Формализация понятия алгоритма. Машина Тьюринга. Функция, вычислимая по Тьюрингу. Функция, правильно-вычислимая по Тьюрингу. Доказательство существования функций, невычислимых по Тьюрингу. Пример невычислимой по Тьюрингу функции. Совпадение класса функций, правильно-вычислимых по Тьюрингу, и класса частично рекурсивных функций.
Формализация понятия алгоритма
Введенного на интуитивном уровне понятия алгоритма и опытным путем установленных свойств алгоритмов достаточно для решения широкого круга математических задач. Достаточно такого подхода и при решении практических задач программирования компьютеров. Однако, в тех случаях, когда задача оказывается сложной и алгоритмическое решение задачи найти не удается, встает вопрос о ее алгоритмической разрешимости. При этом требуется понятие алгоритма формализовать, т.е. четко определить исполнителя алгоритмов, с помощью которого можно провести доказательство алгоритмической неразрешимости задачи. В первой половине XX века почти параллельно было разработаны несколько подходов к формализации алгоритмов – рекурсивные функции, абстрактные машины Тьюринга и Поста, λ-исчисление, нормальные алгорифмы Маркова, впоследствии оказавшиеся эквивалентными. Некоторые из этих подходов оказали воздействие на становление информатики и нашли отражение в языках программирования – таких как, Lisp (λ-исчисление), Рефал (нормальные алгорифмы Маркова). Последний язык используется в исследованиях и разработках в области ИИ.
Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая её, т.е. такая машина Тьюринга, которая вычисляет её значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена.
11 Билет
Формализация понятия алгоритма. Нормальный алгоритм (алгорифм) Маркова. Нормальный алгорифм Маркова в алфавите и над алфавитом. Нормально-вычислимые функции. Примеры нормальных алгорифмов (тождественный нормальный алгорифм, нормальный алгорифм левого присоединения, нормальный алгорифм правого присоединения, нормальный алгорифм удвоения, некоторые арифметические алгорифмы). Основная гипотеза теории алгоритмов в форме Маркова. Эквивалентность определений алгоритма в виде машины Тьюринга и нормального алгоритма Маркова. Универсальный алгоритм Маркова.
В.И.Игошин стр. 354 НАМ.
Формализация понятия алгоритма
Введенного на интуитивном уровне понятия алгоритма и опытным путем установленных свойств алгоритмов достаточно для решения широкого круга математических задач. Достаточно такого подхода и при решении практических задач программирования компьютеров. Однако, в тех случаях, когда задача оказывается сложной и алгоритмическое решение задачи найти не удается, встает вопрос о ее алгоритмической разрешимости. При этом требуется понятие алгоритма формализовать, т.е. четко определить исполнителя алгоритмов, с помощью которого можно провести доказательство алгоритмической неразрешимости задачи. В первой половине XX века почти параллельно было разработаны несколько подходов к формализации алгоритмов – рекурсивные функции, абстрактные машины Тьюринга и Поста, λ-исчисление, нормальные алгорифмы Маркова, впоследствии оказавшиеся эквивалентными. Некоторые из этих подходов оказали воздействие на становление информатики и нашли отражение в языках программирования – таких как, Lisp (λ-исчисление), Рефал (нормальные алгорифмы Маркова). Последний язык используется в исследованиях и разработках в области ИИ.