В теории алгоритмов важное место занимает такое понятие, как машина Тьюринга. Это абстрактный автомат, предложенный еще в 1936 году английским математиком Аланом Матисоном Тьюрингом для исследования вычислимости алгоритмов. Отличительная особенность машины Тьюринга состоит в том, что она является наиболее “тупым” исполнителем: написанная для нее программа может быть перенесена на любое другое вычислительное устройство. Это же понятие используется и при выводе определения алгоритма.
Написание программы, имитирующей работу машины Тьюринга на обычном универсальном компьютере, является довольно интересной задачей, хотя, строго говоря, такая имитация невозможна в полной мере, так как в этом случае в качестве памяти используется бесконечная лента. На нескольких Web-страницах Интернет можно найти программы, имитирующие работу машины Тьюринга, в том числе и написанные на Java. Их можно использовать как наглядные пособия в учебном процессе.
Наиболее оригинальная модель машины Тьюринга, появившаяся в октябре этого года, находится на странице www.nmia.com/~soki/turing. Здесь располагается краткий рассказ о машине и бланк, куда следует вписать задание для нее. Одним словом, посещение указанной страницы представляет интерес как для студентов, так и для преподавателей. Студенты увидят там оживленный вариант скучной страницы учебника, а преподаватели - весьма интересный пример обучения по Интернет. В отличие от моделей на Java программа, имитирующая машину, не загружается в браузер, а располагается на том же сервере, что и страница. Так как задание для машины обычно имеет небольшой объем информации, можно, не ожидая загрузки, сразу же наслаждаться наглядной демонстрацией работы машины Тьюринга. Правда, обратной стороной такого удобства является необходимость находиться в течение всей демонстрации в онлайновом режиме.
Алексей Васильев
