framalex

An online notebook

Эквивалентность машин Тьюринга с разным количеством лент

Оставьте комментарий Posted by framalex на 28 августа, 2012

Теорема 2. Определим МТ с одной лентой как МТ, имеющую единственную ленту, использующуюся в качестве входной, рабочей и выходной. Для каждой $f : (0, 1)^{*} \rightarrow (0, 1)$ и time-constuctable $T : \mathbb{N} \rightarrow \mathbb{N}$ , если f вычислима за $T(n)$ МТ с k лентами, тогда она вычислима и МТ с одной лентой за время $5kT(n)^2$ .

Идея проста. МТ $\bar M$ кодирует k лент машины М на одной ленте, используя позиции $1, k+1, 2k+1, \dots$ чтобы кодировать первую ленту, $2, k+2, 2k+2, \dots$ чтобы кодировать вторую ленту и т.д. Для каждого символа a из алфавита M, $\bar M$ будет содержать символы a и $\bar a$ . При декодировании каждой ленты ровно один символ «надчеркнутым», показывая, что соответствующая считывающая головка МТ М установлена на эту позицию. $\bar M$ не будет менять первые n+1 позиций на ленте (где находятся входные данные), а начнет с $O(n^2)$ шагов для копирования входных данных на оставшуюся часть ленты, кодируя их по ходу этого таким образом.
Для эмуляции одного шага M, МТ $\bar M$ делает два прогона рабочей ленты. Сначала она проматывает ленту слева направо и записывает в регистр состояния k символов, отмеченные надчеркиванием. Затем $\bar M$ использует функцию перехода M, чтобы определить новое состояние, символы и нправление движения считывающих головок и проматывает ленты справа налево, чтобы обновить содержимое ленты. Очевидно, $\bar M$ получает тот же результат, что и M. Также, так как при размере входа n M никогда не занимает больше чем $T(n)$ позиций на любой из лент, то и $\bar M$ никогда не будет использовать больше, чем $2n + kT(n) \le (k+2)T(n)$ своей рабочей ленты, что означает, что на каждые $T(n)$ шагов машины M, машина $\bar M$ выполняет не больше $5kT(n)$ (проматывание ленты вперед и назад требует $5kT(n)$ шагов и дополнительные шаги могут потребоваться для обновления положений считывающих головок).