Как я могу симулировать машину Тьюринга?

Question

Я не совсем понимаю саму идею машины Тьюринга.

В настоящее время мне поручено сделать машину для работы с бобрами. Но на самом деле я не понимаю, что это имитирует ввод. Так какой тип ввода мне моделировать? Например, он спрашивает меня, сколько 1s 3 состояния занятых бобровых машин пишет на ленте? Я уверен, что мне нужно написать машину Тьюринга, но как только она у меня появится, что мне с ней делать?

Какой строкой я должен имитировать ее?

Answer 1

Ваш первый шаг - получить лучшее представление о «самой идее машинного измерения». Вы можете попытаться прочитать об этом:

• Википедия здесь (просто) и здесь
• другое объяснение

Answer 2

Для сценария занятой бобер обычно предполагается, что специального ввода нет, т. Е. Лента машины Тьюринга изначально пуста. Конечно, во время выполнения занятый бобер может записать на ленту и позже прочитать то, что он написал.

Итак, вам нужно смоделировать ленту. Так как он должен быть бесконечным с обеих сторон, я бы предложил реализовать его, создав подклассы ArrayList и переписав методы get() и set(), чтобы сопоставить положительные индексы с четными элементами и отрицательные индексы с нечетными элементами (а также с автоматически увеличивать размер путем повторного вызова add(null), когда есть доступ к индексу за пределами текущего размера списка).