5 Билет

Формализация понятия алгоритма. Понятие алгоритма и вычислимой функции. Невычислимые функции. Качественная и количественная теория алгоритмов. Понятие алгоритмической системы.

Формализация понятия алгоритма

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

6 Билет

Формализация понятия алгоритма. Машина Тьюринга. Определение. Простейшие машины Тьюринга. Тезис Тьюринга. Основная гипотеза теории алгоритмов в форме Тьюринга. Операции на машинах Тьюринга (операция композиции, операция ветвления, операция зацикливания) и их свойства. Базис элементарных машин Тьюринга. Универсальная машина Тьюринга. Недетерминированные машины Тьюринга.

Формализация понятия алгоритма

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

Тезис Тьюринга.

Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т.е. когда она может вычисляться на подходящей машине Тьюринга.