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


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

80 Р. В. Ричи
одну ячейку влево на каждом шаге вычисления. В таком вычислении машина может удлинять ленту влево на столько, на сколько это необходимо. Поэтому здесь удобно считать, что ячейки занумерованы справа налево. Мы уточняем эти замечания в следующих определениях.
Определение 8. Если дана машина Тьюринга Z=(S, m,s0, f) в алфавите Л, мы определяем операцию —+F между мгновенными описаниями Z следующим образом. X-*FY(Z) означает, что выполняется одно из следующих условий, где X и Y—мгновенные описания Z и 0* и &г- — элементы А.
(1) X = (апап.1 ... ом, s, р) и Y = (bnbn-l ... Мо> s', P + 1), где р<пу bi — uj для всех ]Фр и т (ару s) = (bp, s', —1).
(2) X = (anan-i ... а,я0, s, п) и У = (Mn-i • • • я^о» /> « + 1), где т(ап, s) = (bn, f, —I).
(3) X = (anan_l ... a^o, s, /г) и 7 = (РМя-i ... йзд, s', /г + 1), где т(ап, s) = (bnt s', —1) и s'^f.
Определение 9. F-вычисление на машине Тьюринга в алфавите А есть конечная последовательность Хь ..., Xq мгновенных описаний Z, такая, что
(I) Xi-*FXl+i(Z) для всех /=1, ..., q—l и
(II) *! = (*> *о, 0) и ^ = (Г, f,/(/7)).
где t и /' — конечные последовательности элементов А и l(t') означает длину последовательности ?.
Мы говорим, что Х\ начинает вычисление, а Хя является результатом Х\.
Определение 10. Если дано подмножество D множества ТА всех конечных последовательностей элементов алфавита Л, говорят, что функция Ф: D — ТА вычисляется на машине Тьюринга Z, представляющей собой конечный автомат в алфавите Л, если выполняются следующие условия. Для каждого t^D существует F-вычисление на Z, начинающееся с (/, s0,0), причем (Ф(0»М(Ф(0)) есть результат (/,s0, 0).
Когда функция Ф вычисляется на машине Тьюринга Z, представляющей собой конечный автомат, мы говорим о Z как о конечном автомате и о Ф как о функции, вычислимой на этом конечном автомате. Таким образом, когда мы ссылаемся на конечные автоматы, мы подразумеваем просто машины Тьюринга, которые выполняют только /''-вычисления; когда мы говорим о вычислении на конечном автомате Z, мы имеем в виду /''-вычисление на машине Тьюринга Z. Мы будем свободно использовать эту сокращенную терминологию на протяжении всей статьи.
Теорема 1. Если Ф вычисляется конечным автоматом Z с k ^заключительными состояниями, тогда для каждого аргумента

 

1 10 20 30 40 50 60 70 80 81 82 83 84 85 86 87 88 89 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика