Brainfuck на ленте с ячейками неограниченной разрядности

Возьмем машину, у которой система команд точно такая же, как в языке brainfuck, но которая работает на ленте, в ячейки которой можно поместить любые целые числа. Переполнения в арифметических операциях не происходит, команда "+", примененная к положительному числу, всегда даст положительный результат, и т.п. Спрашивается: можно ли работать на такой машине, какие возникнут проблемы и как их обойти?

Преимущества очевидны: раз нет переполнений, то нет нужды и в длинной арифметике, можно одинаково работать с массивами любой длины и т.п. Но довольно быстро мы замечаем, что наш любимый способ очистки ячейки ("[-]") не работает: если в ячейке было отрицательное значение, то программа зацикливается. Аналогично, мы не можем свободно использовать команду копирования "[->+<]" — она тоже работает только для неотрицательных чисел.

Получается, что при программировании нам надо внимательно следить за знаками содержимого ячеек (проще всего — не допускать появления отрицательных чисел вообще), а если возникнет число, знак которого неизвестен — работать с ним специальным образом

Здесь мы рассмотрим две задачи: во-первых, запрограммируем оператор «if(a>b) C; else D;» где a и b неотрицательны, а C и D — какие-то действия, а во-вторых, научимся обнулять, копировать и определять знак произвольного числа.

Условный оператор.

Итак, на ленте записаны два неотрицательных числа a и b (в каких ячейках — мы выбираем сами). Нам надо сравнить эти числа и выполнить, в зависимости от результата, одно из действий C или D. Все использовавшиеся ячейки (включая те, в которых находились a и b) надо обнулить.
Перепишем оператор в таком виде:

h=1; 
while(h){
  if(a==0){ D; a=b=1; h=0; }
  if(b==0){ C; a=b=1; h=0; }
  a--; b--;
} 

Если a и b были неотрицательными, то отрицательных чисел в такой программе появиться не может. Чтобы реализовать оператор if(a==0) B; создадим на ленте блок из 4 ячеек «a 0 1 0» и выполним команды "[>]>>[B>]". Если в начале каретка была на первой ячейке блока, то в конце она окажется на его 4-й ячейке при любом варианте выполнения.

Программа будет выглядеть так (считаем, что каретка и число «a» находятся в ячейке 0, а число «b» — в ячейке 4):

>>+[
  <<[>]>>[C-<<+>>>>[-]+<]
  >[<]<<[D->>+<<<<[-]+>]
  <->>>>-<<]

В качестве переменной h используется единичка из блока «a 0 1 0 b» — все равно после ее обнуления результативных сравнений не будет.

Можно программу слегка упростить, записав ее в виде

h=1; 
while(a){
  if(b==0){ C; a=b=1; h=0; }
  a--; b--;
}
if(h){ D; h=b=0; }

Получится

>>>+<<<
[>[>]>>[C-<<+<[-]+>>>>]
  <<<-<-]
>[-]>>[D-]

Время работы программы — линейное от max(a,b).

Число с неизвестным знаком

Пусть на ленте записано число a, про которое нам неизвестно, положительно оно или отрицательно. Нам его нужно: (1) обнулить, (2) скопировать в другую ячейку и (3) выполнить действие F в случае, если a>0. Будем решать все три задачи вместе.

Как их решать? Примерно так же, как мы ищем ненулевую ячейку на ленте машины Тьюринга, бегать вправо-влево, пока не наткнемся на 0:

if(a){
  x=1;
  while(x){
    y=2*x;
    while(x){
      x--; a++; b--;
      if(a==0) x=y=0;
    }
    x=2*y;
    while(y){
      y--; a--; b++;
      if(a==0){ F; x=y=0; }
    }
  }
}  

Переменная a будет скопирована в b, а действия F выполнены только если исходное значение a было положительным. Перевод на BF:

[>>+<<<<<+
  [ [-<++>>+<]>
    [->->+[>]>>
      [-<<<<[-]<<[-]]
      <<<<<]
    <<[->++>+<<]>>
    [->+>-[>]>>
      [F -<<<<[-]<[-]]
      <<<<<]
    <]]

Время работы — тоже линейно от abs(a). Здесь надо заметить, что в блоках if(a==0) x=y=0; каретка уходит далеко от своего места, да там и остается. Но это не очень важно, поскольку циклы в этот момент заканчиваются.
Что же? Все, что можно было сделать на 8-битной BF-машине, можно сделать здесь? Увы. Есть одна задача, которая машине с бесконечной разрядностью не по зубам. А именно, очистка участка ленты. Если нам не дадут кусочка, который гарантированно заполнен нулями, мы его создать не сможем. Хотя доказывать я это не умею :(