Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

230 Ф. К. Хенни
Теперь предположим, что каждый конечный след, принадлежащий данному левоконечному сегменту ленты t\, принадлежит некоторому другому сегменту /2- Далее предположим, что каждый непереходный след, допускающий для t\, допускающий и для /2. Тогда рассмотрим произвольную ленту, в которой t\ встречается как левоконечный сегмент и на которой машина производит конечные вычисления.
Из теоремы 1 следует, что tz может быть заменен на t\ без изменения результата работы машины над первоначальной лентой или следов, встречающихся в части ленты справа от t\.
Наконец, предположим, что а) каждый след, принадлежащий /1, принадлежит и /2» и обратно; б) каждый непереходный след, допускающий для t\, допускающий и для /2, и обратно. Тогда левоконечные сегменты t\ и t2 можно взаимно заменять без изменения результата вычислений.
Классифицируя левоконечные сегменты ленты в соответствии со следами, которые они имеют, и в соответствии с теми из них, которые являются допускающими, можно показать, что эта классификация порождает классификацию входных слов, соответствующую некоторому автомату.
С. Простые приложения. Теперь поучительно рассмотреть специальный случай, в котором следы, порожденные машиной, не превосходят некоторой длины, скажем /С. Другими словами, машина никогда не проводит в одном и том же квадрате своей ленты более чем /С единиц времени. Легко видеть, что если машина никогда не бывает в любом данном квадрате своей ленты более чем К раз, то существует лишь конечное число различных следов, которые могут встретиться в любом квадрате. Далее, существует только конечное число различных подмножеств этих следов. Если известно подмножество следов, которые могут порождаться машиной в данном квадрате ленты, тогда можно определить подмножество следов, которое может порождаться машиной в следующем квадрате справа. Следовательно, машина может точно с таким же успехом побывать в каждом квадрате точно один раз, передвигаясь по ленте слева направо в соответствии с подмножествами следов. Эта нить рассуждений приводит нас к следующей теореме.
Теорема 2. Если длина каждого следа в каждом вычислении данной одноленточной машины Тьюринга с записью на ленте не превосходит /С, то существует автомат, распознающий в точности то же самое множество входных слов, что и данная машина Тьюринга 1).
]) Утверждение теоремы 2 доказано Б. А. Трахтенбрэтом [4*]; в [7*] установлены близкие друг к другу верхняя и нижняя оценки для числа состояний автомата, существование которого утверждается в теореме 2.—Прим. перев. и ред.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 231 232 233 234 235 236 237 238 239 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика