Нас просят создать машину Тьюринга, которая принимает {0^(2^n); n>0}, то есть , а не общепринятую, опубликованную Майклом Сипсером.
Вместо этого нас просят создать его для алгоритма следующим образом:
- На первом проходеголова, машина Тьюринга вычеркнет один ноль.
- На следующем он вычеркнет еще один ноль.
- На следующем будет вычеркнуто два нуля.
- На следующем, четыре.
Это будет продолжаться таким образом, вычеркивая столько нулей в каждом проходе, сколько было вычеркнуто во всех предыдущих объединенных проходах (1, 1, 2, 4, 8, 16 и т. Д.) до тех пор, пока не останется ни одного нуля и не будет вычеркнуто ни одного (принять) или не останется ни одного нуля, но осталось несколько зачеркнутых (отклонить).
Теперь моя проблема здесь явно связана с тем фактом, что машины Тьюринга не хранят значения данных.Хотя машина Тьюринга может использоваться в качестве счетчика (счетчиков), они не могут затем сохранить подсчитанное значение и воздействовать на него.Я придумал несколько бесконечно длинных недетерминированных машин Тьюринга, которые используют этот алгоритм, но ни один из них не является детерминированным.Мне разрешено использовать столько букв алфавита, сколько необходимо.
Пожалуйста, не спрашивайте меня, почему меня просят создать такую бесполезную машину, учитывая, что эффективный, простой алгоритм уже доступен и широко известен.Я, честно говоря, не могу вам сказать.