Я знаю, например, нахождение целых чисел, где их модуль n равен k, хорошо отображается на конечные автоматы и хорошо опускает работу автоматов для разбора детерминированных грамматик.Мне было интересно, есть ли такие проблемы для машин Тьюринга.
Как уже упоминалось tia , такие вопросы лучше подходят для cs.stackexchange.com .Я бы сказал, что этот вопрос не очень хорошо сформулирован, поскольку обычные компьютеры - это тип машины Тьюринга.Это зависит от того, с какой машиной Тьюринга вы работаете.Например, многие проблемы могут быть решены гораздо быстрее на недетерминированной машине Тьюринга, чем на классическом компьютере (который является детерминированным).