Когда машины Тьюринга имеют конечные состояния?
Это может быть глупый вопрос, но когда у машин Тьюринга есть конечные состояния?
Я вижу некоторых с конечными состояниями, а некоторых нет, я сейчас немного растерялся.
1 ответ
Это зависит от того, как вы определяете машины Тьюринга - это теоретические вещи, где определения могут варьироваться в зависимости от того, какие соглашения вы хотите принять, - но вы можете думать о машине Тьюринга как о принимающих состояниях, таких как, например, DFA и PDA, или как имеющие два фиксированных состояния с именами "остановка принятия" и "остановка отклонения". Я нашел последнее более типичным, но в другом нет ничего удивительного.
ТМ принимают путем принятия состояния: единственный способ, которым я рассматриваю это как полностью общее и простое соглашение, заключается в том, что ТМ принимает любые входные данные, которые приводят к сбою ТМ в состоянии принятия. Сбой ТМ означает ввод конфигурации, для которой переход не определен. В противном случае, если TM аварийно завершает работу в состоянии, которое не принимает или продолжает переходить без остановки, строка не принимается.
ТМ принимают, останавливаясь: это то, что я привык видеть. Здесь под ТМ понимаются особые выделенные состояния halt_accept и halt_reject. Любой TM, входящий в halt_accept, корректно останавливает выполнение и принимает ввод. Любой TM, входящий в halt_reject, корректно останавливает выполнение и отклоняет ввод. Входы, которые приводят к сбою ТМ, всегда интерпретируются как отклоненные, так же как и входы, которые вызывают ТМ для перехода навсегда.
Если вы ищете конвенцию для принятия, я определенно рекомендую последнюю как более типичную. Тем не менее, первое, как правило, следует понимать из контекста.