Я готовлюсь к экзаменам и понятия не имею, как составить таблицу состояний машины Тьюринга, учитывая следующие входные данные 111101 (состояние, ввод/чтение, запись, перемещение, следующее состояние). Любая идея, где я могу получить упрощенные учебники по машинам Тьюринга.
Машина Тьюринга при следующих входных данных: 1010
Ответы (1)
Таблица состояний — это, по сути, программа. Представление того, как машина должна перемещаться между состояниями в зависимости от того, что она читает с ленты и что записывает на ленту при переходе. Его часто визуализируют с помощью кругов (или чего-то подобного) для состояний и стрелок для переходов.
Итак, если я вас правильно понял, то, что вы спрашиваете, это что-то вроде «как должна выглядеть программа, если ввод 111101?» Это не имеет смысла: чтобы разработать программу (таблицу состояний), вам нужно знать, что она должна делать с входными данными, и, вероятно, она должна работать с более чем одним входом.
Вот одно очень краткое введение в машины Тьюринга: https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html
111101
входом для желаемой машины Тьюринга или чем-то еще? - person Codor   schedule 10.05.2016