Абстрактные алгоритмические модели, как уже не один раз отмечалось, употребляются только при построении теории и подтверждении общих параметров алгоритмов. Для практических целей такое представление алгоритмов в большинстве случаев неловко, так…
Имеется запись многоразрядного целого числа п в десятичной системе счисления; выстроить машину Тьюринга, которая обеспечивала бы вычисление значение n + 1. Используем наружный алфавит А = {0,1,...,9, ∆}, в каком…
Машина Тьюринга - это формальная система, порождающая огромное количество собственных конфигураций. Начальным объектом является исходная конфигурация; правилами - многофункциональная таблица. Но ранее была подтверждена эквивалентность представления алгоритмов в разных алгоритмических…
Вернемся к определению предмета науки информатики. Его сравнение с кругом вопросов, обсуждавшихся, а именно, в данном пособии, позволяет узреть колоссальное значение, которое имеет теоретическая информатика для информатики в целом. В…
Как надо из проведенного выше рассмотрения, по уровню формализации представление алгоритмов можно поделить на две группы: естественное и формальное. В группу естественного представления входят некие виды строчной записи и графическая…
Машина Тьюринга состоит из 3-х частей: ленты, считывающая-записывающей головки и логического устройства (рис. 7.1). Лента выступает в качестве наружной памяти; она считается неограниченной (нескончаемой) - уже это свидетельствует о том,…
content