1-ленточная Тьюринг машина и ввод квадратной длинны

[webaib]

День добрый,
есть задача - распознавать ввод квадратной длинны {E}, {a}, {aaaa}, {aaaaaaaaa}
Я довольно легко представляю как это работает с многоленточной машиной - там просто перемножаем (возводим в квадрат) все натуральные числа по очереди, пока длинна ввода не совпадет или не станет меньше. Но с одноленточной машиной не пойму как это провернуть?

[maxal]

Воспользуйтесь тем, что

$$n^2 = 1 + 3 + 5 + \dots + (2n-1).$$

[Профессор Снэйп]

webaib в сообщении #269087 писал(а):

Я довольно легко представляю как это работает с многоленточной машиной - там просто перемножаем (возводим в квадрат) все натуральные числа по очереди, пока длинна ввода не совпадет или не станет меньше. Но с одноленточной машиной не пойму как это провернуть?

А разница? Смоделируйте на одноленточной машине многоленточную. Например, справа от ввода полно свободного места; возводите числа в квадрат там, а затем ходите влево и сравнивайте.

maxal показал очень хороший способ последовательного получения квадратов.

[webaib]

Да, спасибо. Я уже нашед эту формулу и с ней все решил )

[webaib]

Посмотрите что навоял, может что упростить?
http://www.filefactory.com/file/a2b0ea4/n/asd.rar файликом для JFLAP

[Профессор Снэйп]

Какой ужас! Вас что, всегда заставляют машины Тьюринга в виде автомата рисовать? Почему просто не написать список команд?

[webaib]

Да нет, достаточно только спецификации, просто так наглядно и JFLAP посмотреть как работает автомат на различных вводах.

[Профессор Снэйп]

webaib в сообщении #269339 писал(а):

просто так наглядно

У нас разные представления о наглядности

[webaib]

Скачайте JFLAP и вы поймете, что я имею в виду.

[Профессор Снэйп]

webaib в сообщении #269423 писал(а):

Скачайте JFLAP и вы поймете, что я имею в виду.

Где (лень искать)?

[webaib]

http://www.jflap.org/jflaptmp/oct11-09/JFLAP.jar