Машина Тьюринга, деление на 2

[ujh]

Доброго времени суток.

Подскажите, пожалуйста, как написать алгоритм для деления числа на 2, используя алфавит только из 0 и 1.
Вход: 0111110, к примеру.

Спасибо!

[Joker_vD]

Система счисления унарная или двоичная? Если двоичная, то все до неприличия просто. Если унарная и можно пользовать дополнительные символы: заменяйте все две идущие подряд единицы на одну, потом вернитесь в начало и уплотните.

[ujh]

Joker_vD в сообщении #573083 писал(а):

Система счисления унарная или двоичная? Если двоичная, то все до неприличия просто. Если унарная и можно пользовать дополнительные символы: заменяйте все две идущие подряд единицы на одну, потом вернитесь в начало и уплотните.

В случае с двоичной решение - сдвиг, это понятно. Я забыл указать, что система счисления унарная.
С дополнительными символами я так и предполагал решение, но преподаватель запрещает использовать их. А без дополнительных символов я не представляю, как отличить начало ленты от 0 между 1. За помощью с этим и обращаюсь.
Или с таким алфавитом ее невозможно решить?

[venco]

А состояний много можно?

[ujh]

venco в сообщении #573124 писал(а):

А состояний много можно?

Неограниченно, но предполагается, что это нужно написать не более чем за 10-15 минут. Более 20 состояний, думаю, уже будет перебор.

[venco]

Можно два нуля в начале сделать...

[Сургонт Е Ф]

ujh в сообщении #573121 писал(а):

А без дополнительных символов я не представляю, как отличить начало ленты от 0 между 1.

Ноль между единицами всегда один. Лента ведь бесконечная, то есть слева и справа неограниченное количество нулей, так? Значит, если при обратном движении каретки встретились два нуля подряд, то?

[venco]

Сургонт Е Ф в сообщении #573246 писал(а):

ujh в сообщении #573121 писал(а):

А без дополнительных символов я не представляю, как отличить начало ленты от 0 между 1.

Ноль между единицами всегда один. Лента ведь бесконечная, то есть слева и справа неограниченное количество нулей, так? Значит, если при обратном движении каретки встретились два нуля подряд, то?

Я полагаю, о содержимом до и после ничего не известно. Но два нуля в начале можно себе обеспечить сразу.

[Сургонт Е Ф]

venco в сообщении #573327 писал(а):

Я полагаю, о содержимом до и после ничего не известно. Но два нуля в начале можно себе обеспечить сразу.

Ну, обычно в задачах о машине Тьюринга, если не оговорено обратное, лента предполагается бесконечной в обе стороны и пустой. (Это пусть ujh уточнит) Но если в данном случае это не так, то да, нужно специально отмечать начало числа. Можно двумя нулями, можно двумя единицами.

[ujh]

venco в сообщении #573327 писал(а):

Но два нуля в начале можно себе обеспечить сразу.

Сдвинуться влево и поставить там 0?

Сургонт Е Ф в сообщении #573333 писал(а):

Ну, обычно в задачах о машине Тьюринга, если не оговорено обратное, лента предполагается бесконечной в обе стороны и пустой. (Это пусть ujh уточнит) Но если в данном случае это не так, то да, нужно специально отмечать начало числа. Можно двумя нулями, можно двумя единицами.

А если она все-таки пустая, то у нас нет прав записи/чтения в те ячейки?

[venco]

ujh в сообщении #574361 писал(а):

venco в сообщении #573327 писал(а):

Но два нуля в начале можно себе обеспечить сразу.

Сдвинуться влево и поставить там 0?

Нет. Заменять на ноль первую единицу каждой пары, а не вторую.

[Сургонт Е Ф]

ujh в сообщении #574361 писал(а):

А если она все-таки пустая, то у нас нет прав записи/чтения в те ячейки?

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

[ujh]

venco, Сургонт Е Ф
Огромное спасибо за помощь.