1^3^n для n>=1 машина Тьюринга
Я хочу сделать машину Тьюринга, которая принимает строки с длиной 1, равной 3. 111, 111111111, 111111111111111111111111111, и так далее. Но я не могу сделать алгоритм для этого. До сих пор я могу сделать машину, которая принимает длину, кратную 3. Пожалуйста, помогите мне
2 ответа
Как и в любой задаче программирования, ваша цель состоит в том, чтобы разбить задачу на более мелкие проблемы, которые вы можете решить, решить их и собрать по кусочкам, чтобы ответить на более сложную задачу. Есть много способов сделать это, в общем, и вам просто нужно найти тот, который имеет смысл для вас. Тогда и только тогда вы должны беспокоиться о том, чтобы получить "лучшую" и "более быструю" программу.
Что делает число степенью три?
- число один - это степень трех (3^0)
- если число является степенью три, три раза это число является степенью три (x = 3^k => 3x = 3^(k+1)).
Мы можем "обратить" направление 2 выше, чтобы дать рекурсивное, а не индуктивное определение: число является степенью три, если оно делится на три, а число, деленное на три, является степенью три: (3 | x && x / 3 = 3^k => x = 3^(k+1)).
Это предполагает машину Тьюринга, которая работает следующим образом:
- Проверьте, есть ли у ленты один. Если так, остановитесь, примите.
- В противном случае разделите на три, сбросьте головку ленты в начало и начните сначала.
Как мы можем разделить на три? Ну, мы можем сосчитать один, а затем стереть два после него; при условии, что мы уничтожим вдвое больше, чем рассчитывали, у нас будет ровно одна треть первоначального числа. Однако, если у нас заканчиваются те, которые нужно стереть, мы знаем, что число не делится на три, и мы можем остановить-отклонить.
Это наш дизайн. Сейчас настало время для реализации. У нас будет две фазы: первая фаза будет проверять случай одной; другая фаза будет делиться на три и сбрасывать головку ленты. Когда мы разделим, мы сотрем их, введя новый символ ленты B, который мы можем отличить от пустой ячейки #. Это будет важно, чтобы мы могли помнить, где начинается и заканчивается наш ввод.
Q T | Q' T' D
----------+-----------------
// phase one: check for 3^0
----------+-----------------
q0 # | h_r # S // empty tape, not a power of three
q0 1 | q1 1 R // see the required one
q0 B | h_r B S // unreachable configuration; invalid tape
q1 # | h_a # L // saw a single one; 1 = 3^0, accept
q1 1 | q2 1 L // saw another one; must divide by 3
q1 B | q1 B R // ignore previously erased ones
----------+-----------------
// prepare for phase two
----------+-----------------
q2 # | q3 # R // reached beginning of tape
q2 1 | q2 1 L // ignore tape and move left
q2 B | q2 B L // ignore tape and move left
----------------------------
// phase two: divide by 3
----------------------------
q3 # | q6 # L // dividing completed successfully
q3 1 | q4 1 R // see the 1st one
q3 B | q3 B R // ignore previously erased ones
q4 # | h_r # S // dividing fails; missing 2nd one
q4 1 | q5 B R // see the 2nd one
q4 B | q4 B R // ignore previously erased ones
q5 # | h_r # S // dividing fails; missing 3rd one
q5 1 | q3 B R // see the 3rd one
q5 B | q5 B R // ignore previously erased one
----------+-----------------
// prepare for phase one
----------+-----------------
q6 # | q0 # R // reached beginning of tape
q6 1 | q6 1 L // ignore tape and move left
q6 B | q6 B L // ignore tape and move left
В этом могут быть некоторые ошибки, но я думаю, что идея должна быть в основном разумной.
Проверьте длину входа (111, 111111111,...) скажем, strLen. Убедитесь, что результат log(strLen) для базы 3 равен целому числу.
то есть в коде:
bool is_integer(float k)
{
return std::floor(k) == k;
}
if(is_integer(log(strLen)/log(3))){
//Then accept the string as it's length is a power of 3.
}