Чтобы явно определить операции, производимые нашим устройством, для начала пронумеруем его внутренние состояния, например: 0,1,2,3,4,5. Тогда действия нашего устройства, или машины Тьюринга, полностью определялись бы неким явным списком замен, например:
00 → 00R
01 → 131L
10 → 651R
11 → 10R
20 → 01R.STOP
21 → 661L
30 → 370R
• •
• •
• •
2100 → 31L
• •
• •
• •
2581 → 00R.STOP
2590 → 971R
2591 → 00R.STOP
Выделенная цифра слева от стрелки — это символ на ленте, который устройство в данный момент считывает. Оно заменяет этот символ выделенной цифрой в середине справа от стрелки. R означает, что устройство должно переместиться вдоль ленты на один квадрат вправо, a L соответствует такому же перемещению влево. (Если, в соответствии с исходным представлением Тьюринга, мы полагаем, что движется не устройство, а лента, то R означает перемещение ленты на один квадрат влево, a L — вправо.) Слово STOP означает, что вычисления завершены и устройство должно остановиться. Например, вторая инструкция 01 → 131L говорит о том, что если устройство находится в начальном состоянии 0 и считывает с ленты 1, то оно должно перейти в состояние 13, оставить на ленте тот же символ 1 и переместиться по ленте на один квадрат влево. Последняя же инструкция 2591 → 00R.STOP говорит о том, что если устройство находится в состоянии 259 и считывает с ленты 1, то оно должно вернуться в состояние 0, стереть с ленты 1, т. е. записать в текущий квадрат 0, переместиться по ленте на один квадрат вправо и прекратить вычисления.
Вместо номеров 0, 1, 2, 3, 4, 5…. для обозначения внутренних состояний мы можем — и это более соответствовало бы знаковой системе нанесения меток на ленту — прибегнуть к системе нумерации, построенной только на символах «0» и «1». Состояние n можно было бы обозначить просто последовательностью из n единиц, но такая запись неэффективна. Вместо этого мы используем двоичную систему счисления, ставшую теперь общепринятой:
0 → 0,
1 → 1,
2 → 10,
3 → 11,
4 → 100,
5 → 101,
6 → 110,
7 → 111,
8 → 1000,
9 → 1001,
10 → 1010,
11 → 1011,
12 → 1100 и т. д.
Здесь последняя цифра справа соответствует «единицам» точно так же, как и в стандартной (десятичной) системе записи, но цифра прямо перед ней показывает число «двоек», а не «десятков». В свою очередь третья цифра справа относится не к «сотням», а к «четверкам»; четвертая — к «восьмеркам», а не к «тысячам» и т. д. При этом разрядность каждой последующей цифры (по мере продвижения влево) дается соответственной степенью двойки: 1, 2, 4 (= 2 х 2), 8 (= 2 х 2 х 2), 16 (= 2х2х2х2), 32 (= 2x2x2х2х2). (В дальнейшем нам будет иногда удобно использовать в качестве основания системы счисления числа, отличные от «2» и «10». Например, запись десятичного числа
