Здравствуйте, kapezc.
Предлагаю Вашему вниманию программу для машины Тьюринга (надеюсь, что с самой машиной Тьюринга Вы знакомы)
Алгоритм такой - отрабатываем два раза следующие шаги:
1) идем вправо и заменяем все 1 на #, в конце добавляем признак конца *
2) идем влево, пока не найдем 0 или 1, делаем шаг вправо
3) если *, то все прошли: ставим 0 и заканчиваем (либо на вторую половину, либо останов), если #, то восстанавливаем 1, делаем шаг вправо и на 4
4) ищем вправо признак конца *
5) идем вправо, пока не найдем 0 - меняем на 1, делаем шаг влево
6) ищем влево * и на шаг 2
[table]
[row][col][/col][col]
0
[/col][col]
1
[/col][col]
*
[/col][col]
#
[/col][col][/col][/row]
[row][col]
1
[/col][col]
* Л 2
[/col][col]
# П 1
[/col][col]
-
[/col][col]
-
[/col][col]Заменяем все 1 на #, в конце ставим *[/col][/row]
[row][col]
2
[/col][col]
0 П 3
[/col][col]
1 П 3
[/col][col]
-
[/col][col]
# Л 2
[/col][col]Ищем влево либо 0, либо 1[/col][/row]
[row][col]
3
[/col][col]
-
[/col][col]
-
[/col][col]0 П 7[/col][col]1 П 4[/col][col]Если *, то меняем на 0, и идем на повтор еще одной последовательности, если #, то меняем на 1 и идем на поиск конца, т.е. *[/col][/row]
[row][col]
4
[/col][col]
-
[/col][col]
-
[/col][col]* П 5[/col][col]# П 4[/col][col]Ищем *[/col][/row]
[row][col]
5
[/col][col]
1 Л 6
[/col][col]
1 П 5
[/col][col]
-
[/col][col]
-
[/col][col]Пропускаем 1, в конце добавляем еще одну 1[/col][/row]
[row][col]
6
[/col][col]
-
[/col][col]
1 Л 6
[/col][col]
* Л 2
[/col][col]
-
[/col][col]Ищем влево * и на поиск очередной #[/col][/row]
[row][col]
7
[/col][col]
* Л 8
[/col][col]
# П 7
[/col][col]
-
[/col][col]
-
[/col][col]7-12 строки полностью повторяют строки 1-6[/col][/row]
[row][col]
8
[/col][col]
0 П 9
[/col][col]
1 П 9
[/col][col]
-
[/col][col]
# Л 8
[/col][col][/col][/row]
[row][col]
9
[/col][col]
-
[/col][col]
-
[/col][col]0 Н 0[/col][col]1 П 10[/col][col]Единственное отличие - по звездочке будет останов[/col][/row]
[row][col]
10
[/col][col]
-
[/col][col]
-
[/col][col]* П 11[/col][col]# П 10[/col][col][/col][/row]
[row][col]
11
[/col][col]
1 Л 12
[/col][col]
1 П 11
[/col][col]
-
[/col][col]
-
[/col][col][/col][/row]
[row][col]
12
[/col][col]
-
[/col][col]
1 Л 12
[/col][col]
* Л 8
[/col][col]
-
[/col][col][/col][/row]
[/table]
В результате из последовательности, например, 1111 получим 11110111101111
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен