Проектирование таблицы состояний машины Тьюринга

Question

Есть ли в них какие-либо полезные рекомендации по описанию того, что делает машина Тьюринга, если у вас уже есть псевдокод для алгоритма?

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

Редактировать

Я не хочу создавать симулятор машины Тьюринга, я хочу описать машину Тьюринга на бумаге (алфавит, состояния, переходы) для определения некоторого языка.

Вот тривиальный пример того, что я имею в виду, скажем, мне нужно написать машину Тьюринга, которая перебирает строку из 0 и 1 и изменяет все 0 в ней на 1.Например, если вы начинаете с 11010 на ленте (ввод), то заканчиваете с 11111 на ленте (вывод).Теперь на языке высокого уровня, который вы знаете, это что-то вроде:

Go over every character on tape
    If character is 0 change it to 1

Неофициально описание машины Тьюринга выглядит примерно так:

У вас есть два состояния: q и halt.Когда вы перейдете в состояние q и увидите цифру 1, перейдите вправо, не меняя ее.Если вы видите 0, измените его на 1 и перейдите к справа.Если вы видите пустой символ (конец ленты), перейдите в состояние остановки .

Формально у вас будет что-то вроде {q, halt} для состояний.{((q, 1) -> (q, 1, R)), ((q, 0) -> (q, 1, R)), ((q, #) -> (halt, 0, L))} для переходов.

Теперь эта проблема тривиальна, но есть другие, которые более сложны (добавление унарных чисел или распознавание языка с равным количеством a, b и c).Я мог бы легко написать псевдокод для них, но написание машины Тьюринга гораздо сложнее (занимает у меня много времени), и мне было интересно, есть ли какие-нибудь советы, ресурсы или рекомендации, которые помогут мне стать лучше в решении подобных задач.

Answer 1

Отказ от ответственности: Ваш вопрос очень общий, следовательно, и этот ответ тоже.Обратите внимание, что я далеко не эксперт по TMS, и этот подход обычно не очень эффективен (я даже не могу обещать, что он всегда будет эффективным).Я просто набросал здесь несколько мыслей.

Я бы предложил попробовать подобный подход:Возьмите свой псевдокод и сократите его так, чтобы он состоял только из а) логических переменных и б) if-заявления.Например:

if THIS_LETTER_IS("A"):
    found_an_even_number_of_A = not found_an_even_number_of_A

if THIS_LETTER_IS("Q") and previous_letter_was_X and found_an_even_number_of_A
        and not checking_for_alternative_2:
    # can't be a word of alternative 1, so check for alternative 2
    going_back_to_start_to_check_for_alternative_2 = True

if going_back_to_start_to_check_for_alternative_2:
    MOVE_TO_PREVIOUS
else:
    MOVE_TO_NEXT

if going_back_to_start_to_check_for_alternative_2 and THIS_LETTER_IS(EMPTY):
    # reached the beginning, so let's check for alternative 2
    going_back_to_start_to_check_for_alternative_2 = False
    checking_for_alternative_2 = True

Когда у вас есть вложенные ifs, замените их на ands;удалить else блокирует с помощью not:

if something:
    if something_else:
        do_a
    else:
        do_b

становится

if something and something_else:
    do_a

if something and not something_else:
    do_b

Каждый if тогда блок должен содержать только один MOVE_TO_PREVIOUS или MOVE_TO_NEXT, возможно , WRITE команда и любое количество назначений переменных.

Завершите все if положения , такие , что все до единого ваши логические значения и текущего письма всегда проверять, дублирование блоки, где необходимо.Пример:

if something and something_else:
    do_a

становится

if THIS_LETTER_IS("A") and something and something_else and something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("A") and something and something_else and not something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("Q") and something and something_else and something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("Q") and something and something_else and not something_i_dont_care_about_here:
    do_a

Теперь, если у вас есть n логические значения и m письма, у вас должны быть m * 2ⁿ ifs.Просто представьте, что вы сохранили логические значения в битовом поле, поэтому каждая возможная комбинация логических значений представляет целое число .Следовательно, вышесказанное становится

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and bitfield[2]:
    do_a

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and not bitfield[2]:
    do_a

# ...

который затем становится

if THIS_LETTER_IS("A") and bitfield == 7:
    do_a

if THIS_LETTER_IS("A") and bitfield == 3:
    do_a

# ...

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

Я надеюсь, что все вышесказанное имеет смысл.

Answer 2

Вам нужен готовый к использованию инструмент, симулятор машины Тьюринга?Есть такие довольно много доступных.Или на самом деле вы хотите сделать свой собственный?Кажется, это допустимая реализация в JavaScript: http://klickfamily.com/david/school/cis119/TuringSim.html вы могли бы довольно легко проанализировать код и перевести его на C или C ++.