Архив категории ‘Классические формализации понятия «алгоритм»’

Нормальные алгоритмы Маркова

    На этом шаге мы рассмотрим нормальные алгоритмы Маркова.     Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.     Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.     Рассмотрим […]

Машина Тьюринга

    На этом шаге мы дадим общую характеристику машине Тьюринга.     Машина Тьюринга подобна машине Поста, но функционирует несколько иначе. Машина Тьюринга (МТ) состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q0, […]

Машина Поста

На этом шаге мы рассмотрим машину Поста. Абстрактные (т.е. существующие не реально, а лишь в воображении), машины Поста и Тьюринга, предназначенные для доказательств различных утверждений о свойствах программ для них, были предложены независимо друг от друга (и практически одновременно) в 1936 г. американским математиком Эмилем Постом и английским математиком Алланом Тьюрингом. Эти машины представляют собой […]

Подходы к формализации понятия «алгоритм»

    На этом шаге мы рассмотрим подходы к формализации понятия "алгоритм".     Теперь нужно предложить способ описания шагов алгоритма. Известно несколько подходов к формализации понятия «алгоритм»: теория конечных и бесконечных автоматов; теория вычислимых (рекурсивных) функций; лямбда-исчисление Черча.     Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма […]

Точное понятие алгоритма

    На этом шаге мы рассмотрим точное понятие алгоритма.     Следующая задача заключается в том, чтобы ввести точное, формальное понятие алгоритма. Как заметил Э.Дейкстра в книге «Дисциплина программирования», преимущество формального способа записи состоит в том, что он дает нам возможность изучать алгоритмы как математические объекты; при этом формальное описание алгоритма служит основой, позволяющей нам интеллектуально […]