Время Брэйди

Машина, стирающая много единиц, работает по тому же принципу, но никогда не может остановиться. Да и как она может остановиться, если в какой-нибудь не исследованной области ленты окажется еще одна единица? Бобры-работяги были построены П. Марино из г. Трой (шт. Нью-Йорк) и Д. Капланом из

г. Дир-Парк (шт. Нью-Йорк). Марино решил также задачу очистки ленты, описав свои передвигающиеся единицы как «веники», подметающие ленту.

Р. Робинсон из Калифорнийского университета в Беркли написал для своего персонального компьютера фирмы IBM программу, моделирующую машину Тьюринга. Наблюдая, как предложенный У. Шультом бобр-работяга записывал свою 501-ю единицу, Робинсон заметил, что, прежде чем остановиться, программа порождала повторяющуюся и все время удлиняющуюся последовательность чередующихся 0 и…

1.  Начиная с чистой ленты, программа порождала такие последовательности длиной 0, 6, 13, 28, 48, 78, 121, 190, 289, 442 и 667 символов. В последней последовательности насчитывалась 501 единица. Робинсон решил исследовать повеление машины Шульта, когда она начинает работать не с чистой ленты, а с одной из последовательностей чередующихся 0 и 1. Начав с последовательности длиной 9 символов (из которых 5 символов — единицы), машина остановилась после 12 870 233 шагов, породив последовательность, содержащую 4911 единиц. Для этого объем памяти должен быть в 3 раза больше и необходимо в 25 раз больше шагов, чем в том случае, когда машина Шульта начинает с чистой ленты. Робинсона смутил тот факт, что сравнительно небольшое изменение во входных данных приводит к такому странному поведению машины. «Мне кажется, — пишет Робинсон, — что эти результаты заставляют сомневаться в справедливости ограничений Шульта на объем памяти и время».

По-видимому, Б. Вайман из Боннского университета не был первооткрывателем бобра-работяги с четырьмя состояниями. А. Брэйди из Университета шт. Невада в Рено построил свою версию автомата за 10 лет до Вай- мана. В то время Брэйди был сотрудником Университета шт. Орегон.

 

0 Коментариев

Вы можете быть первым =)

Оставить коментарий