Машина Тьюринга. Целая часть от деления

[Sonatia]

Помогите пожалуйста найти целую часть от деления числа n на 3. Число n записано набором единиц.

[eoln]

Сообщение от Sonatia

Число n записано набором единиц.

1 = 1
11 = 2
111 = 3
Это так чтоли? Если да, то length(inttostr(s)) div 3

[Sonatia]

Спасибо. Это конечно понятно. Только вот как бы это в командах машины Тьюринга оформить?

[notHaker]

ничего не понял... поясните подробней

[Sonatia]

Задание:Докажите вычислимость функции f(x)=[2x/3], где [] – целая часть числа. Данное число записано набором единиц.
Составить программу для машины Тьюринга

[Sonatia]

С умножением разобралась, а с делением и нахождением целой части проблема

[Грымзик]

Машину Тьюринга несколько лет назад проходили, так что написать не могу, но я бы реализовывала такую идею.
Сначала отправилась бы в конец слова, поставила бы после него специальный символ, вернулась бы к концу слова, отсчитала бы три единицы, заменяя их пустыми символами (через состояния отсчитать три единицы легко).
т.е примерно так
q0 1 -> _, q1, left
q1 1 -> _, q2, left
q2 1 -> _, q3, nikuda
дальше идем направо, пока не дойдем до специального символа, доходим до конца единиц после него (вначале там вообще единиц не будет), ставим один, и опять возвращаемся к концу первого слова, чтобы отсчитать тройки.
q3 _ -> q3,_,right
q3 # -> q4,#,right
q4 1 -> q4,1,right
q4 _ -> q5, 1, left
q5 1 -> q5, 1, left
q5 # - > q6, #, left
q6 _ -> q6,_,left
q6 1 -> q0, 1, nikuda
И надо рассмотреть, когда единиц 3 уже не насчитается.

[Sonatia]

Огромнейшее спасибо