\documentclass[11pt]{article}
\usepackage{amsthm,amsfonts,amsmath}
\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}
%\def\B{\mathbb{B}}
\oddsidemargin 3mm
\topmargin -3mm
\textwidth 142 mm
\textheight 210 mm

\newcommand\B{\{0,1\}}
\newcommand\Z{\mathbb{Z}}
\newcommand\N{\mathbb{N}}
\newcommand\poly{\text{poly}}
\newcommand{\pair}[1]{\langle #1 \rangle}
\newtheorem{thm}{Теорема}
\newtheorem{lemma}{Лемма}
\theoremstyle{definition}
\newtheorem{define}{Определение}
\theoremstyle{remark}
\newtheorem{remark}{Замечание}

\date{}

\title{Экологические машины Тьюринга}

\begin{document}
\maketitle

\section {Введение}

Рабочий алфавит машины Тьюринга обычно отличается от её входного
алфавита~--- он содержит разнообразные дополнительные символы, от
простых ограничительных до нескольких копий входного алфавита с
разными пометками. В настоящих же компьютерах память~--- это просто
последовательность бит, поэтому трюки с добавлением символов в рабочий
алфавит выглядят искусственными. Кроме того, хотя есть различные типы
памяти, обычно не рассматривают одни из них как ``входную память'', а
другие как ``рабочую память''.

В данном тексте рабочий алфавит будет равняться входному
алфавиту. Вход будет записываться на рабочей ленте, и не будет никаких
дополнительных лент. Мы называем такие машины ``экологическими''
потому, что они должны работать на входе, не загрязняя его
промежуточными результатами своих вычислений.

Вход записан на ленте с начала, и не ограничен каким-либо
маркером. Клетки ленты, не занятые входом, могут содержать
произвольные символы. Вычисление должно давать один и тот же
результат, независимо от того, что записано в этих клетках.

Очевидно, если экологическая машина выдаёт некоторый результат на
входе~$x$, то она выдаёт тот же результат на любом входе~$x'$,
продолжающем~$x$ (так, что $x' = x y$). Поэтому функции, вычислимые на
экологических машинах~--- префиксные функции.

Мы представим четыре основных резульата. Первые три
(теоремы~\ref{thm-1-bounded},~\ref{thm-3} и~\ref{thm-2}) сравнивают
вычислительную силу экологических машин с обычными машинами
Тьюринга. Четвёртый результат (теорема~\ref{thm4}) о том, как
вычисления изменяют вычислительную среду. В качестве вычислительной
среды мы рассматриваем содержимое памяти перед началом вычислений; мы
соотносим такую модель с моделью вычислений с оракулом. 

Сначала мы рассмотрим вопрос: ``Эквивалентны ли экологические машины
обычным машинам Тьюринга при вычислении префиксных функций?'' Основной
результат состоит в отрицательном ответе на этот вопрос для
экологических машин с одной лентой, бесконечной в одну сторону:
существует вычислимая префиксная функция, невычислимая на такой
экологической машине. При доказательстве будет важно, что конец
входных данных никак не отмечен на ленте. Если существует
ограничительный символ для обозначения этого конца, то экологическая
модель эквивалентна обычной, даже если машина может лишь читать этот
символ, но не может записывать его на ленту.

Аналогичные вопросы мы рассматриваем для машин с несколькими лентами и
для машин с лентами, бесконечными в обе стороны. Вход экологической
машины с $s$~лентами, бесконечными в одну сторону~--- это
$s$~слов, записанных на лентах. Мы покажем, что в отличие от случая
$s=1$, для любого $s\ge 2$ экологическая модель эквивалентна обычной.

В случае машины с $s$~лентами, бесконечными в обе стороны, вход
машины~--- это набор $2s$ слов, записанных на лентах справа и слева от
начальной позиции головки. Для всех~$s$ эта модель слабее обычной:
существует вычислимая функция $2s$ аргументов, невычислимая на
экологической машине с $s$~лентами, бесконечными в обе стороны. Здесь
важно, что на каждой ленте записано два слова. Если хотя бы одна лента
содержала только одно слово, область с противоположной стороны от
головки можно было бы использовать для хранения промежуточных
результатов, и вычислительная модель было бы эквивалентна обычной.

Также мы докажем следующий факт: существует тотальная (невычислимая)
функция~$f$ из $\B^{*}$ в $\B$ и бесконечная в обе стороны
последовательность~$\alpha$ такие, что $f$~вычислима
с оракулом~$\alpha$, но не вычислима на экологической машине со
специальной входной лентой длины, равной длине входа, и бесконечной в
обе стороны лентой, содержащей последовательноть~$\alpha$.

\section{Экологические машины с лентами, бесконечными в одну сторону}

Обозначим через $\B^{*}$ множество всех конечных двоичных
последовательностей.

Сначала рассмотрим машины Тьюринга с одной лентой, бесконечной в одну
сторону и ленточным алфавитом $\{0,1,\$\}$, которым не разрешено
записывать н аленту символ $\$$. Перед началом вычислений на ленте
записано $x\$$ в $|x|+1$ самых левых клетках. Остальные клетки
содержат произвольные символы. Для простоты рассмотрим машины, выход
которых~--- либо~0, либо~1, точнее, которые имеют два завершающих
состояния, $s_0$ и~$s_1$. Машина останавливается, если попадает в одно
из этих двух состояний, и её выход~--- 0, если она остановилась в
состоянии~$s_0$, и~1, если она остановилась в состоянии~$s_1$. В
каждый момент машина может узнать, находится ли головка в крайней
левой позиции ленты. (Для обычных машин этой оговорки не делается,
поскольку они могут отметить конец ленты специальным маркером.)

Мы говорим, что такая машина вычисляет функцию $f\colon\B^{*}\to\B$,
если для каждого~$x$ из области определения~$f$ машина выдаёт $f(x)$
на входе $x\$$ независимо от того, какие символы записаны на ленте
справа от входа. Если $f(x)$ не определено, поведение машины может быть
любым. 

\begin{lemma}
  Любая частичная вычислимая префиксная функция $f\colon\B^{*}\to\B$
  может быть вычислена такой машиной.
\end{lemma}
\begin{proof}
  Рассмотрим обычную машину Тьюринга~$M$ (без ограничений на ленточный
  алфавит), вычисляющую функцию~$f$. Путь ленточный алфавит~$M$
  содержит $m$~символов. Выберем такое~$k$, что $2^k>m$ и постром
  экологическую машину~$N$ описанного вида, моделирующую
  работу~$M$. Закодируем каждый символ алфавита~$M$ двоичной
  последовательностью длины~$k$, не используя в качестве кода
  последовательность $0^k$. Будем записывать содержимое ленты~$M$
  соответствующими блоками по $k$ бит на ленте машины~$N$, а блоком
  $0^k$ будем представлять первую клетку, на которой машина~$M$ ещё не
  была. Записанное таким образом содержимое ленты~$M$ будет
  располагаться сразу за маркером $\$$, обозначающим конец входа.

  Моделирование происходит обычным образом. Единственное нетривиальное
  действие~--- копирование входа в область моделируемой ленты. Это
  делается так: сначала мы копируем первый символ, заменяя его (в
  начале ленты) на~1. Затем копируем второй, третий, и т.д., каждый
  раз оставляя область входа в виде $00\dots01$, где первая единица
  стоит на месте только что скопированного символа. Таким образом,
  следущий символ, который надо копировать, следует за первой единицей
  слева.
\end{proof}

Теперь рассмотрим ту же модель вычислений, но на этот раз вход не
будет ограничен маркером. Ленточный алфавит равен $\B$, все клетки
справа от входа могут содержать произвольные символы, машина знает,
находится ли говорка в самой левой клетке ленты. Машина имеет два
конечных состояния, $s_0$ и~$s_1$.

Мы говорим, что такая машина~$M$ вычисляет частичную
функцию~$f\colon\B^*\to\B$, если для любого~$x$ из области
определения~$f$ машина~$M$ на любом входе вида $x{*}{*}{*}\dots$
(звёздочки означают любой символ из $\B$) останавливается в состоянии
$s_{f(x)}$. Если~$f(x)$ не определено, поведение машины может быть
произвольным.

Мы называем такие машины \emph{экологическими машинами Тьюринга с
одной лентой, бесконечной в одну сторону}. Очевидно, всякая такая машина
вычисляет частичную префиксную фукнцию $f\colon\B^*\to\B$.

\begin{thm}\label{thm-1-bounded}
  Существует вычислимая частичная префиксная функция $f\colon\B^*\to\B$,
  невычислимая на экологической машине Тьюринга с одной лентой,
  бесконечной в одну сторону.
\end{thm}
\begin{proof}
  Пусть $g\colon\N\to\N$~--- вычислимая функция, растущая достаточно
  быстро (далее мы увидим, насколько быстро). Рассмотрим следующую
  функцию~$f$: она определена на всех словах~$x$ вида $x=0^k 1 y u v$,
  где $|y|=2^{g(k)}$, $|u|=g(k)$, а $v$~--- любое
  слово. Рассмотрим~$u$ как двоичную запись числа~$n$. На таком входе
  $f(x)=1$, если $n$-ый бит слова $y$ равен~1, и 0 в противном случае.

  Очевидно, $f$~--- вычислимая префиксная функция. Неформально говоря,
  экологическая машина не может вычислять~$f$ потому, что пока головка
  движется до того места, где записано~$n$, машина должна где-то
  записывать расстояние между текущим положением головки и началом
  записи~$n$. Поэтому ей придётся испортить часть входа.

  Предположим, что функция~$f$ вычисляется некоторой машиной нужного
  типа. Выберем большое~$k$ и слово~$y$ длины $2^{g(k)}$. Предположим,
  что слово~$y$ содержит как единицы, так и нули. Запустим машину на
  входе $0^k1y000\dots$. В некоторый момент времени~$\tilde t$ машина
  впервые попадёт на клетку, где начинается запись~$n$, то есть на
  клетку номер $N=k+1+2^{g(k)}+1$. Мы утверждаем, что $\tilde t$ много
  больше, чем~$N$.

  Пусть~$k<i<N$~--- граница между двумя соседними клетками ленты
  ($k$~--- это граница между последним нулём и единицей в слове
  $0^k$). Рассмотрим последовательность состояний, в которых машина
  пересекала эту границу (мы рассматриваем вычисления только до
  момента~$\tilde t$). Эта последовательность называется \emph{следом
  на границе}~$i$. Мы докажем, что следы на всех границах различны.

  \begin{lemma}
    Если машина останавливается на всех входах вида $0^k1\alpha$ (где
    $\alpha\colon\N\to\B$ произвольна), а на входе~$I$ этого вида
    впервые достигает клетки~$N>k+1$ в момент времени~$\tilde t$, то
    все следы этого вычисления до времени~$\tilde t$ на всех
    границах~$i$ таких, что $k<i<N$ различны.
  \end{lemma}

  Предположим, что лемма уже доказана. 

  Пусть слово~$y$ длины~$2^{g(k)}$ содержит как нули, так и
  единицы. Тогда на входе $0^k1y000\dots$ машина в какой-то момент
  времени достигнет клетки~$N=k+1+2^{g(k)}+1$. По лемме все следы
  этого вычисления различны. Путь машина имеет
  $Q$~состояний. Количество различных следов длины не больше~$l$ равно
  $Q^0+Q^1+\dots+Q^{l-1}$, что меньше, чем $Q^l$. Полагая~$l$ равным
  $\frac{g(k)-1}{\log_2 Q}$, мы получаем, что по крайней мере половина
  следов имеют длину большую, чем~$\frac{g(k)-1}{\log_2 Q}$. Поэтому
  машина достигает границы~$N$ не раньше, чем через
  $\frac{(g(k)-1)2^{g(k)}}{\log_2 Q}$ шагов после начала
  вычислений. Все конфигурации машины до этого момента различны
  (конфигурация~--- это содержимое первых $2^{g(k)}+k+1$ клеток ленты,
  состояние машины и положение головки на ленте). Наборы конфигураций
  для различных~$y$ также различны, так как начав работу в любой
  конфигурации и подставляя разлиные значения~$n$, мы можем найти всё
  слово~$y$.

  Таким образом, число конфигураций для всех~$y$ не меньше, чем
  $$
  \frac{(2^{2^{g(k)}}-2)2^{g(k)}(g(k)-1)}{\log_2 Q}.
  $$
  С другой стороны, общее число возможных конфигураций~---
  $$
  Q\cdot 2^{k+1+2^{g(k)}}(k+1+2^{g(k)}).
  $$
  Опуская мультипликативные константы (не зависящие от~$k$), мы видим,
  что первое число равно $2^{2^{g(k)}+g(k)}g(k)$, а второе~---
  $2^{2^{g(k)}+g(k)+k}$. Их отношение, таким образом,
  $g(k)/2^k$. Полагая $g(k)$ равным, например, $2^{2k}$, мы получаем
  противоречие, если~$k$ достаточно велико.

  Остаётся только доказать лемму.

  \begin{proof}
    Предположим, что следы вычисления на входе~$I$ на границах $i>k$ и
    $i+j$ совпадают для некоторого $j>0$. Обозначим~$w$ часть входа
    слева от границы~$i$, и $v$~--- часть входа между границами $i$ и
    $i+j$. Мы докажем, что машина не останавливается на входе
    $wvvv\dots$. 

    Обозначим~$A$ вычисление на входе~$I$ и $B$~--- вычисление на
    входе $wvvv\dots$. Пусть след вычисления~$A$ на границах $i$ и
    $i+j$~--- $q_1$, $q_2$, \dots, $q_n$. Мы указывает только
    состояния, в которых машина пересекает границу, а направления
    очевидны: на нечётных позициях слева направо, на чётных~--- справа
    налево. 

    Разделим ленту на зоны. Зона~$0$ начинается у левого конца ленты и
    продолжается до границы~$i$, зона~1~--- от границы $i$ до
    границы~$i+j$, зона~2~--- от $i+j$ до~$i+2j$ и т.д.

    Мы будем сравнивать вычисление~$B$ внутри зоны~$k$ с
    вычислением~$A$ внутри зоны~$p(k)$, где
    $$
    p(k)=\left\{
    \begin{array}{l}
      0, \text{ если $k=0$,} \\
      1, \text{ если $k\ne 0$.}
    \end{array}\right.
    $$
    Мы будем говорить, что \emph{вычисление~$B$ корректно в момент~$T$
    относительно зоны~$k$}, если существует момент времени~$t$ в
    вычислении~$A$ такой, что
    \begin{enumerate}
      \item[a.]
	Содержимое зоны~$k$ в вычислении~$B$ в момент~$T$
	совпадает с содержимым зоны~$p(k)$ в вычислении~$A$ в
	момент~$t$.

      \item[b.]\label{itemb}
	В вычислении~$A$ обозначим через~$l$ количество пересечений
	левой границы зоны~$p(k)$ до момента~$t$ (если $p(k)=0$, $l$
	не определено), и через~$m$ количество пересечений правой
	границы этой зоны. Тогда в вычислении~$B$ на момент~$T$
	случилось ровно~$l$ пересечений левой
	границы зоны~$k$, в состояниях $q_1,\dots, q_l$, и ровно~$m$
	пересечений правой границы зоны~$k$, в состояниях
	$q_1,\dots,q_m$. Из этого следует, в частности, что если в
	вычислении $A$ в момент~$t$ головка находится слева от (справа
	от, внутри) зоны~$p(k)$, то в момент~$T$ вычисления~$B$
	головка находится слева от (справа от, внутри) зоны~$k$.

      \item[c.]
	Если в момент~$T$ в вычислении~$B$ головка находится внутри
	зоны~$k$ над $m$-ой клеткой этой зоны в состоянии~$q$, то в
	момент~$t$ вычисления~$A$ головка находится над $m$-ой клеткой
	зоны~$p(k)$ в том же состоянии~$q$.
    \end{enumerate}
    
    Докажем по индукции, что вычисление~$B$ корректно в любой момент
    времени относительно любой зоны. База индукции очевидна. Докажем
    шаг индукции.

    Предположим вначале, что в момент~$T+1$ головка остаётся в той же
    зоне~$k$, в которой она была в момент~$T$. По предположению
    индукции, вычисление~$B$ корректно в момент~$T$ относительно
    зоны~$k$. Тогда существует такой момент~$t$, что состояния
    машины в вычислении~$B$ в момент~$T$ и в вычислении~$A$ в
    момент~$t$ совпадают. Значит, совпадают также и состояния, позиции
    головок и содержимые лент в моменты $T+1$ и~$t+1$. Таким образом,
    $B$~корректно в момент~$T+1$ относительно зоны~$k$. Корректность
    относительно других зон, очевидно, не нарушается.

    Далее, предположим, что машина в момент~$T$ пересекает границу
    между зонами, например, переходит из зоны~$k$ в
    зону~$k+1$. Рассмотрим, по предположению индукции для зоны~$k$,
    соответствующий момент времени~$t_k$ в вычислении~$A$. В
    момент~$t_k+1$ вычисления~$A$ головка машины покидает зону~$p(k)$,
    переходя в зону~$p(k)+1$ в состоянии~$q_{m+1}$ (где $m$~---
    число из пункта~b). В вычислении~$B$ в момент~$T$ содержимое
    зоны~$k$ совпадает с содержимым зоны~$p(k)$ в момент~$t_k$
    вычисления~$A$. Поэтому в вычислении~$B$ головка также выходит за
    границу зону в том же состоянии~$q_{m+1}$. Значит, вычисление~$B$
    корректно в момент времени~$T+1$ относительно зоны~$k$
    с~$t=t_k+1$.

    Докажем, что в этом случае вычисление также корректно в
    момент~$T+1$ относительно зоны~$k+1$. В этот момент головка
    приходит в зону~$k+1$ слева. По предположению индукции вычисление
    корректно в момент~$T$ относительно зоны~$k+1$, значит, в
    некоторый момент~$t$ в вычислении~$A$ содержимое зоны~$p(k+1)=1$
    совпадает с содержимым зоны~$k+1$ в момент~$T$ вычисления~$B$. При
    этом до момента~$t$ в вычислении~$A$ головка в последний раз
    пересекала правую границу зоны в состоянии~$q_m$, левую~--- в
    состоянии~$q_l$, и в момент~$t$ находилась слева от зоны (здесь
    $l$ и~$m$~--- числа из пункта~b). Только что мы видели, что в
    момент~$T+1$ вычисления~$B$ головка входит в зону~$k+1$ в
    состоянии~$q_{l+1}$. Положим~$t'$ равным тому моменту времени
    вычисления~$A$, когда головка пересекает границу~$i$ в $l+1$-й раз
    (слева направо). В этот момент содержимое зоны~1 в вычислении~$A$
    совпадает с содержимым зоны~$k+1$ в момет~$T+1$ вычисления~$B$, и
    также совпадают состояния машин (они равны~$q_{m+1}$). Таким
    образом, вычисление~$B$ в момент~$T+1$ корректно относительно
    зоны~$k+1$ (с данным значением~$t'$).

    Аналогично разбирается случай, когда головка переходит из зоны~$k$
    в зону~$k-1$.

    Итак, доказательство по индукции завершено.

    Поскольку вычисление~$B$ корректно во все моменты времени
    относительно всех зон, можно заключить, что оно
    бесконечно. Действительно, в каждый момент времени в
    вычислении~$B$ состояние машины совпадает с состоянием машины в
    некоторый момент времени вычисления~$A$ (до момента~$\tilde t$), а
    среди этих состояний нет завершающего состояния. Таким образом,
    машина в вычислении~$B$ никогда не оказывается в завершающем
    состоянии.
  \end{proof}    
\end{proof}

Теперь перейдём к машинам с $k$~лентами, бесконечными в одну
сторону. Такая машина получает~$k$ входов, записанных по одному на
каждой ленте. Она вычисляет функцию $f\colon(\B^{*})^k\to\B$, если для
каждого $x=(x_1,\dots,x_k)$ из области определения~$f$ машина
останавливается в состоянии~$s_{f(x)}$, начав работать, когда на
каждой ленте~$i$ было записано слово~$x_i$, а за ним~--- произвольные
символы. Если $f(x)$ не определено, поведение машины может быть
любым. Такую машину мы называем \emph{экологической машиной Тьюринга с
$k$~лентами, бесконечными в одну сторону}. Очевидно, всякая
машина такого вида вычисляет некоторую вычислимую частичную префиксную
функцию $f\colon(\B^{*})^k\to\B$.

\begin{thm}\label{thm-3}
  Для любого~$k>2$ всякая вычислимая частичная префиксная функция
  $f\colon(\B^{*})^k\to\B$ вычислима на экологической машине с
  $k$~лентами, бесконечными в одну сторону.
\end{thm}

\begin{proof}
  Определим ещё одну вычислительную модель~--- вариацию машины со
  счётчиками. Такая машина состоит из управляющего устройства с
  конечным числом состояний и нескольких счётчиков. Счётчики хранят в
  каждый момент времени неотриуательное целое число и умеют по команде
  управляющего устройства увеличивать и уменьшать своё числе на
  единицу, а также выяснять, равно ли оно нулю. Ещё у машины есть $k$
  бесконечных в одну сторну лент, головки на которых могут двигаться
  только направо. Эта модель отличается от экологической модели в
  условии теоремы тем, что у неё есть счётчики, но она не может
  возвращать головки налево.

  Вход такой машины~--- $k$ двочных слов, записанных на лентах. После
  входов на лентах записаны произвольные символы.

  \begin{lemma}\label{lem-C-counters}
    Существует такая константа~$n$, что любая вычислимая частичная
    префиксная функция $f\colon(\B^*)^k\to\B$ вычислима на машине
    указанного вида с~$n$ счётчиками.
  \end{lemma}

  \begin{proof}
    Заметим, что если у нас есть достаточн много счётчиков, мы можем
    выполнять любые арифметические действия. Например, чтобы сложить
    числа в счётчиках $A$ и~$B$, надо увеличивать~$A$, одновременно
    уменьшая~$B$, пока $B$ не станет нулём. Тогда в~$A$ мы получим
    сумму начальных значений $A$ и~$B$. Аналогично выполняется
    вычитание. Умножение и деление сводится к сложению и
    вычитанию. Таким образм, мы может проверять числа на простоту и
    находить простые числа в порядке возрастания.

    Пусть теперь $f\colon(\B^*)^k\to\B$~--- вычислимая частичная
    префиксная функция. Она вычислима на обычной машине Тьюринга~$M$ с
    $k$~лентами, бесконечными в одну сторону, головки на которых могут
    двигаться только направо и одной дополнительной рабочей лентой
    (головка на которой может читать и записывать информацию, и
    двигаться как направо, так и налево; поскольку эта лента в начале
    вычислений не содержит входа, мы можем использовать её как обычную
    память). Нам достаточно моделировать эту машину на нашей машине со
    счётчиками, чтобы доказать лемму.

    Для этого мы будем в одном из счётчиков держать закодированное
    состояние рабочей ленты машины~$M$, в другом~--- номер клетки этой
    ленты, над которой находится головка, а остальные использовать для
    промежуточных вычислений. Кодирование осществляется так: пусть
    содержимое ленты~--- $t_1 t_2 \dots t_N$. Тогда значение счётчика
    равно $2^{t_1} 3^{t_2}\dots p_N^{t_N}$, где $2$, $3$, \dots,
    $p_N$~--- последовательные простые числа.
    
    Перемещение головки соответствует увеличению или уменьшению
    счётчика, содержащего позицию головки, а запись нуля или единицы в
    $i$-ю клетку ленты~--- делению или умножению кода ленты на
    соответствующее число~$p_i$. Перемещение головок на любой из
    $k$~входных лент моделируется напрямую -- перемещением
    соответствующей головки на соответствующей ленте.
  \end{proof}

  \begin{lemma}\label{lem-2-counters}
    Любая вычислимая частичная префиксная
    функция~$f\colon(\B^*)^k\to\B$ вычислима на машине описанного выше
    вида с двумя счётчиками.
  \end{lemma}

  \begin{proof}
    По лемме~\ref{lem-C-counters} для некоторого~$C$ существует машина
    с $C$~счётчиками, вычисляющая~$f$. Закодируем значения этих
    счётчиков одним числом~$S=2^{c_1}3^{c_2}\ldots p_n^{c_n}$, где,
    как и раньше, через $p_i$ обозначено $i$-е простое число, а через
    $c_i$ обозначено значение $i$-го счётчика. Будем хранить число~$S$
    в первой из двух счётчиков, а второй использовать для
    промежуточных вычислений.

    Если моделируемая машина увеличивает значение~$i$-го счётчика на
    единицу, мы должны умножить число~$S$ на $p_i$. Поскольку есть
    лишь конечное число моделируемых счётчиков, список чисел~$p_i$
    конечен, известен заранее и может быть записан в управляющем
    устройстве моделирующей машины. Поэтому мы уменьшаем на~1 значение
    первого счётчика (содержащего в начале число~$S$), увеличивая
    $p_i$ раз на~1 значение второеп счётчика, до тех пор, пока
    значение первого счётчика не станет равным нулю. После этого
    значение второго счётчика кодирует новое состояние моделируемой
    машины. Аналогично выполняется деление на~$p_i$ и проверка
    делимости (то есть выяснение, равно ли значение некоторого
    счётчика нулю).

    Операции с головками на входных лентах опять моделируюся напрямую.
  \end{proof}

  Заметим, что моделирующая машина в доказательстве
  леммы~\ref{lem-2-counters} обладает следующим свойством: она
  перемещает головки на входных лентах только в состоянии, когда один
  из счётчиков пуст. Назовём машины, обладающие этим свойством,
  \emph{корректными}.

  Для доказательства теоремы нам достаточно научиться моделировать
  корректную машину~$M$ с двумя счётчиками и $k$~входными лентами на
  экологической машине~$N$ с $k$~лентами. Рассмотрим случай
  $k=2$. Пусть содержимое первой ленты машины~$M$ есть $t_1 t_2\dots$,
  положение головки на первой ленте~--- $i$, содержимое второй ленты~---
  $s_1 s_2\dots$, положение головки~--- $j$, содержимое счётчиков~---
  $C_1$ и~$C_2$. Тогда содержимое первой ленты моделирующей машины~$N$
  равно $00\dots 01 t_{i+1} t_{i+2}\dots$, второй~--- $0\dots01 s_{j+1}
  s_{j+2}\dots$, положение головки на первой ленте~--- $C_1$, на
  второй~--- $C_2$.

  Если машина~$M$ увеличивает или уменьшает значение счётчика,
  машина~$N$ просто двигает соответствующую головку. Поскольку~$N$
  знает, находится ли головка в начале ленты, она знает, равен счётчик
  нулю или нет. Теперь рассмотрим случай, когда машина~$M$ двигает
  головку на одной из лент. В этот момент (поскольку $M$~корректна)
  значение одного из счётчиков равно нулю, поэтому одна из головок
  машины~$N$ стоит в начале ленты. Если $M$ двигает головку на другой
  ленте, $N$~сначала переписывает значение счётчика (не равного нулю)
  в другой счётчик (равный нулю). После этого нужная головка
  оказывается в начале ленты, и $N$ может дойти до первой единицы,
  заменить её на ноль, считать следующий символ, заменить его на
  единицу и вернуть головку в начало ленты, таким образом
  смоделировав очередной шаг~$M$.

  Для $k>2$ моделирование аналогично.
\end{proof}

\begin{remark}
  Важно, что машина~$N$ в приведённом доказательстве знает, находится
  ли головка в начале ленты. Если бы такой информации у неё не было, и
  требовалось бы, чтобы она не пыталась выйти за пределы ленты, то
  модель вычислений была бы слабее обычной. Это можно доказать
  методом, похожим на использованный ниже в доказательстве
  теоремы~\ref{thm-2}. 
\end{remark}


\section{Экологические машины с лентами, бесконечными в обе стороны}

Рассмотрим теперь экологические машины, ленты которых бесконечны в обе
стороны. Мы записываем по два входных слова на каждой ленте: одно с
одной стороны от начального положения головки, другое с другой. Если
бы хотя бы на одной ленте с одной стороны не было входного слова,
машина могла бы использовать эту часть ленты как рабочую, и
получившаяся модель вычислений была бы эквивалентна обычной. Поэтому
мы рассмотриваем вариант, когда у машины есть $s$~лент и $2s$~входных
слов.

\begin{thm}\label{thm-2}
  Для любого $s\ge1$ существует вычислимая частичная префиксная
  функция $f\colon(\B^*)^{2s}\to\B$, невычислимая на экологической
  машине с~$s$ лентами, бесконечными в обе стороны.
\end{thm}

\begin{proof}
  Сначала докажем утверждение теоремы для $s=1$. Рассмотрим следующую
  функцию~$f(x,y)$. Она определена на всех словах $x$, $y$ вида
  $y=0^k1z u v$, $x=r w$, где $|r|=|z|=2^{2k}$,
  $|u|=2k+1$. Рассмотрим~$u$ как двоичную запись числа~$n$ от 0 до
  $2^{2k+1}-1$. Тогда $f(x,y)=1$, если $n$-й бит слова $rz$ равен
  единице, и 0 в противном случае.
  
  Неформально говоря, экологическая машина не может вычислять~$f$
  потому, что пока головка движется от начала ленты до места, где
  записано~$n$, машина должна хранить расстояние, которое осталось
  пройти, и поэтому должна испортить часть слова~$rz$. 

  Выберем $k$, $r$, $z$, $P$ так, что $P$~--- число от~1 до~$2^{2k}$,
  а $r$ и~$z$~--- двочиные слова длины~$2^{2k}$. Запустим машину,
  записав слева от начала ленты~$r$, а справа $0^k1z$, и рассмотрим
  первый момент~$T$, когда головка выйдет за позицию~$P$ или $-P$
  (позиция $-P$~--- это $P$-я клетка слева от начала ленты). Обозначим
  через~$a$ содержимое ленты от позиции~$-2^{2k}$ до позиции головки,
  и через $b$ содержимое ленты от головки до позиции~$2^{2k}+k+1$ (в
  момент времени~$T$). Обозначим через~$q$ состояние машины в этот
  момент. Чтобы получить противоречие, мы докажем, что $r$, $z$ и~$P$
  можно найти по паре~$\pair{q,ba}$, если $rz$ не состоит из
  блоков~$00$ и~$11$.

  Чтобы сделать это, найдём границу между $b$ и~$a$ и~$ba$ следующим
  образом: будем пробовать все способы деления слова~$ba$ на слова
  $b'$ и~$a'$ подряд, начиная со способа дающего самое длинное
  $b'$. Для каждого деления и для всех $n\le |rz|$ запустим машину,
  начиная с состояния~$q$, записав на ленту слева от головки $ba$, а
  срава $b'n$. Выходы машины для всех~$n$ соберём в строку
  $r'z'$. Если выбранное слово~$b'$ длиннее настоящего~$b$ (то есть
  $b'=bb''$), $r'z'$ будет состоять из блоков $00$
  и~$11$. Действительно, машина будет считать $b''$ старшими
  битами~$n$, поэтому её результат не будет зависеть от (одного или
  нескольких) младших битов настоящего~$n$. Поэтому чётные биты ответа
  будут совпадать с соответствующими нечётными, и полученное
  слово~$r'z'$ будет состоять из блоков $00$ и~$11$. Это просто
  проверить. В этом случае мы считаем, что деление на~$b'$ и~$a'$
  неправильно, и переходим к следующему, до тех пор, пока правильное
  деление не будет найдено. 

  Количество таких различных троек $\pair{r,z,P}$, что $rz$ не состоит
  из блоков $00$ и~$11$, равно $(2^{2^{2k+1}}-2^{2^{2k}})2^{2k}$, а
  количество пар~$\pair{q,ba}$ равно $Q2^{2^{2k+1}+k+1}$, где
  $Q$~обозначает количество состояний машины. Для достаточно
  больших~$k$ мы получаем противоречие, поскольку количество
  пар~$\pair{q,ba}$ оказывается меньше количества троек
  $\pair{r,z,P}$.

  Это доказательство обощается и на
  случай~$s>1$. Функцию~$f(x_1,y_1,\dots,x_s,y_s)$ следует определять
  так: она определена, если $y_1=0^k1z_1u_1v_1$, $x_1=r_1w_1$, и
  $y_i=z_iu_iw_i$, $x_i=r_iw_i$ для $i>1$; здесь $|r_i|=|z_i|=2^{2k}$,
  $|u_i|=2k+1+\lceil\log_2 s\rceil$. Рассмотрим~$y_i$ как двоичную
  запись числа~$n_i$ и обозначим через~$n$ сумму всех $n_i$ по
  модулю~$s2^{2k+1}$. Тогда~$f(x_1,y_1,\dots,x_s,y_s)$ равно $n$-му
  биту строки $Z=r_1z_1\dots r_sz_s$.

  Доказательство надо изменить так: рассмотрим
  кортеж~$\pair{r_1,z_1,\dots,r_s,z_s,P}$, где $P$~--- число из
  $1,\dots,2^{2k}$, и найдём первый момент времени, когда хотя бы одна
  из головок машины выйдет за позицию $P$ или~$-P$ на своей ленте.

  Слова $a_i$ и~$b_i$ определяются так же, как раньше: $a_i$~---
  содержимое $i$-й ленты от позиции $-2^{2k}$ до головки, а $b_i$~---
  от головки до позиции~$2^{2k}$. (Или $2^{2k}+k+1$, если $i=1$).

  Чтобы получить противоречие, надо доказать, что $Z$ и~$P$ можно
  найти по~$\pair{q,b_1a_1,\dots,b_{s}a_{s}}$, если $Z$ не состоит из
  блоков $00$ и~$11$. Для этого мы находим $a_i$ и~$b_i$ для
  каждого~$i$ по очереди так: разделяем $b_ia_i$ на $b_i'$ и~$a_i'$,
  начиная с самого длинного~$b_i'$. Для каждого деления запускаем
  машину, записывая на всех лентах, кроме $i$-й, слова
  $b_1a_1,\dots,b_{s}a_{s}$ как слева от головки, так и справа. На
  $i$-й ленте слева от головки пишем~$b_ia_i$, а справа $b_i'n$ (по
  очереди перебирая все $n\le s2^{2k+1}$). Если $b_i'$ длиннее
  настоящего~$b_i$, то полученное слово~$Z'$ будет состоять из блоков
  $00$ и~$11$, и мы поймём, что деление неправильно. Если деление
  правильное, то полученное слово~$Z'$ будет представлять собой
  циклический сдвиг настоящего слова~$Z$, поэтому не будет состоять из
  таких блоков. 
\end{proof}

\section{Вычисления с оракулом}

Теперь рассмотрим экологические машины Тьюринга следующего типа: они
имеют обычную ленту конечной длины для записи входа (длина ленты равна
длине входа, на ленте действует считывающе-записывающая головка,
которая может перемещать по ленте направо и налево, машина знает,
находится ли головка у начала или конца ленты). Кроме этого, у машины
есть бесконечная в обе стороны лента, в начале вычислений содержащая
последовательность~$\alpha$. Обе ленты имеют двоичный алфавит.

\begin{thm}\label{thm4}
  Существует тотальная функция~$f\colon\B^{*}\to\B$ и двустороняя
  двоичная последовательность~$\alpha$ такие, что
  $f$~вычислима относительно~$\alpha$, но невычислима на экологической
  машине описанного типа, на бесконечной ленте которой записана
  последовательность~$\alpha$.
\end{thm}

\begin{proof}
  Рассмотрим следующую функцию~$f^\alpha(x)$.  Пусть
  $k=|x|$. Обозначим через~$y$ последовательность~$\alpha$,
  ограниченную на отрезок $[-k^2+1,k^2]$, а через~$u$~---
  последовательность~$\alpha$, ограниченную на отрезок $[k^2+1,
  k^2+l]$, где $l=\lceil\log(2k^2+k)\rceil$.  Рассмотрим~$u$ как
  двоичную запись числа~$n$ между $-k^2+1$ и~$k^2$. Тогда
  $f^\alpha(x)=1$ если $n$-ый бит слова $yx$ равен единице, и $0$ в
  противном случае.

  Очевидно, для каждого~$\alpha$ функция~$f^\alpha(x)$ вычислима
  относительно~$\alpha$. Чтобы определить~$\alpha$ так, чтобы~$f^\alpha(x)$
  не была вычислима на экологической машине, мы воспользуемся методом
  диагонализации. 
  
  Выберем какую-нибудь нумерацию экологических машин: $M_1,M_2,\dots$.
  Пусть $z$~--- отображение из отрезка~$[-n,m]$ в $\B$. Будем
  говорить, что двусторонняя последовательность $\alpha:\Z\to\{0,1\}$
  \emph{продолжает} $z$, если $\alpha(i)=z(i)$ для всех $i$ в области
  определения~$z$. Аналогично, функция~$z'$, определённая на некотором
  отрезке $\Z$ продолжает функцию~$z$, определённую на другом отрезке,
  если $z'(i)=z(i)$ для всех~$i$ из области определения~$z$.

  \begin{lemma}
    Для всякой $z_0$ существует такие~$x$ и~$z$, что
    $z$~продолжает~$z_0$ и для всякого $\alpha$, продолжающего~$z$,
    машина~$M_1$ либо не останавливается на входе~$\pair{x,\alpha}$,
    либо даёт неправильный результат.
  \end{lemma}
  
  \begin{proof}
    Рассмотрим два случая.

    Первый случай. Существует слово~$x$ и отоборажение~$z$,
    продолжающее~$z_0$, такие, что для всякой двустороней
    последовательности~$\alpha$, продолжающей $z$, машина не
    останавливается на входе $\pair{x,\alpha}$. В этом случае
    утверждение леммы очевидно.

    Второй случай: для всякого слова~$x$ и отображения~$z$,
    продолжающего~$z_0$, существует такая последовательность~$\alpha$,
    продолжающая $z$, что машина на входе~$\pair{x,\alpha}$
    останавливается.

    Утверждение. В этом случае существуют такие $x,y,n,\alpha$, что
    $y$~продолжает~$z_0$, $\alpha$~продолжает~$yn$, слова $x$, $y$
    и~$n$ имеют вид, указанный в определении~$f^\alpha$, и машина даёт
    неправильный ответ на входе~$x,\alpha$, то есть не выдаёт $n$-ый бит
    слова $yx$. Очевидно, в таком случае машина просматривает только
    конечную часть последовательности~$\alpha$, и можно положить~$z$
    равным общему продолжению~$yn$ и просмотренной части~$\alpha$.

    Докажем утверждение. Предположим, что оно не верно. Выберем
    достаточно большое~$k$ и положим~$x$ равным двоичной строке
    длины~$k$. Пусть $y$~--- функция из $[-k^2+1,k^2]$ в~$\B$,
    продолжающая~$z_0$. Выберем число~$P$ между $1$ и~$k^{2}$.
    Запустим машину на входе $x$, записав на бесконечной ленте~$y$, и
    нули на остальных местах. Рассмотрим первый момент времени, когда
    головка на бесконечной ленте выйдет за клетку~$P$ или
    $-P$. Обозначим через $a$ и~$b$ содержимое ленты, соответственно,
    от позиции  $-k^{2}+1$ до положения головки, и от положения
    головки до позиции~$k^{2}$. Обозначим через~$q$ состояние машины
    в этот момент, через $m$ позицию головки на входной (конечной)
    ленте, а через~$w$~--- содержимое входной ленты.

    Чтобы получить противоречие, докажем, что $x$, $y$ и~$P$ можно
    найти по ~$\pair{q,ba,m,w}$, если $yx$ не состоит из блоков $00$
    и~$11$. Найдём правильное деление $ba$ на $a$ и~$b$ следующим
    образом. Будем пробовать все возможные деления на~$b'$ и~$a'$,
    начиная с самого длинного~$b'$. Назовём деление \emph{допустимым},
    если для каждого~$n\le|yx|$ существуют $\beta$ и~$\gamma$
    ($\beta$~--- бесконечная налево двоичная последовательность,
    $\gamma$~--- бесконечная направо двоичная последовательность)
    такие, что машина останавливается, если её запустить в
    состоянии~$q$, записав на рабочей ленте~$\beta bab'n\gamma$, на
    входной ленте~$w$, и установив головку на входной ленте в
    позицию~$m$, а на рабочей~--- между $\beta ba$ и
    $b'n\gamma$. Очевидно, правильное деление допустимо, и, более
    того, машина выдаёт в этом случае верный результат для
    любых~$\beta,\gamma$. Из предположения следует также, что всякое
    деление с $|b'|>|b|$ тоже допустимо. Действительно,
    положим~$b'=bb''$, $n'$ равным числу, двоичная запись которого
    есть конкатенация $b''$ и $l-|b''|$~старших битов $n$, где $l$~---
    длина двоичной записи~$n$. По предположению, существуют такие
    $\beta,\gamma$, что машина останавливается на $x,\beta
    byb''n\gamma$. Вычисления машины, начиная с состояния~$q$, когда
    на рабочей ленте записано $\beta bab'n\gamma$, на входной
    ленте~$w$, головка на рабочей ленте стоит между $ba$ and $b'$, а
    на входной ленте в позиции~$m$, являются частью вычислений на
    входе~$x$ с $\alpha=\beta byb''n\gamma$, поэтому машина
    останавливается.

    Более того, для любых $\beta,\gamma$, если машина останавливается,
    то результат её работы равен $n'$-му биту $yx$. Действительно, мы
    можем записать~$\alpha$ как $\alpha=\beta byn'n''\gamma$, где
    $n''$ состоит из младших $|b''|$ битов~$n$. А мы
    предполагаем, что на любой последовательности~$\alpha$,
    продолжающей~$yn'$, если машина останавливается на~$x,\alpha$, то
    она даёт $n'$-й бит~$yx$.


    \begin{center}
      \begin{tabular}{c|c|c|c|c|c|c|c}
	\multicolumn{1}{c}{\hskip  20mm   \hskip  10mm}    &
	\multicolumn{1}{c}{\hskip  15mm    \hskip  15mm}    &
	\multicolumn{1}{c}{\hskip  10mm   \hskip  10mm}   &
	\multicolumn{1}{c}{\hskip  10mm      \hskip  10mm}  &
	\multicolumn{1}{c}{\hskip  3mm    \hskip  3mm} &
	\multicolumn{1}{c}{\hskip  3mm    \hskip  3mm} &
	\multicolumn{1}{c}{\hskip  3mm    \hskip  3mm}  &
	\multicolumn{1}{c}{\hskip  5mm   \hskip  5mm}   \\
	\hline
	$\beta$   &
	$b$   &
	\multicolumn{2}{|c|}{$y$}&
	$b''$  &
	\multicolumn{2}{|c|}{$n$} &
	$\gamma$   \\
	\hline
	
	$\beta$   &
	$b$   &
	\multicolumn{2}{|c|}{$y$}&
	\multicolumn{2}{|c|}{$b''n'$}&
	$n''$ &
	$\gamma$   \\
	\hline
	\multicolumn{8}{c}{Начальное содержимое ленты, представленное в двух видах}\\
	\multicolumn{8}{c}{\hskip 1mm\phantom{g}}\\
	\hline
	
	$\beta$   &
	$b$   &
	$a$   &
	\multicolumn{2}{|c|}{$b'$}&
	\multicolumn{2}{|c|}{$n$} &
	$\gamma$   \\
	\hline
	\multicolumn{8}{c}{Содержимое ленты в момент, когда головка находится
	  в позиции $P$ или~$-P$}\\
	
      \end{tabular}
    \end{center}
    
    Для каждого деления $a',b'$, начиная с $b'=ba$ и для всех~$n$
    найдём произвольные $\beta, \gamma$, и из результатов
    вычислений для всех~$n$ найдём~$y'x'$. Если окажется, что $b'$
    длиннее, чем нужно, полученное слово~$y'x'$ будет состоять из
    блоков $00$ и~$11$, и такое делеение можно отвергнуть. Первое
    деление, не отвергнутое этим процессом, и будет правильным.

    Осталось сравнить число $Qk2^{2k^2+k}$ различных
    четвёрок~$\pair{q,ba,l,w}$ и число
    $$
    k^2(2^{2k^2+k-|z_0|}-2^{(2k^2+k-|z_0|)/2})
    $$
    различных троек $\pair{x,y,P}$.
  \end{proof}

  Очевидно, утверждение леммы справедливо не только для машины~$M_1$,
  но и для любой экологической машины. Поэтому доказательство
  продолжается так: найдём такие~$x_1, z_1$, что машина~$M_1$ даёт
  неправильный результат, потом найдём~$x_2,z_2$, так, что
  машина~$M_2$ даёт неправильный результат, и при этом $z_2$
  продолжает~$z_1$, и так далее. Потом положим $\alpha$ равной общему
  продолжению всех~$z_i$.
\end{proof}



\end{document}