Как узнать, является ли машина Тьюринга решающим?

Question

Есть ли простой способ приблизиться к этому? Могу ли я найти, является ли это решающим, посмотрев на диаграмму машины Тьюринга?

Answer 1

Решитель - это машина, которая останавливается на всех входах. There is no general way to prove whether a given machine halts on all inputs.

Если у вас есть конкретная машина, вы можете попытаться официально доказать, что все пути остановки выполнения. Например, если считываемая головка вашего компьютера всегда перемещается прямо на каждом переходе (никогда не остается) и останавливается при отсутствии ввода, то для всех конечных входов машина останавливается. Более простым примером может быть машина, которая имеет только одно состояние: остановка.

Answer 2

TM решает язык L тогда и только тогда 1- струн L положить M в ПРИНЯТЬ состояние 2 строки NOT IN L M положить в Reject состояние

TM M распознает язык L тогда и только тогда 1- струн L поместить М в ПРИНЯТЬ состояние 2 строки НЕ в L - ЯВНО поместить М в Отклонить состояние - или вызвать М к петле

@Wanhui Его вы говорите «TM изменяется между двумя государствами и одновременно государства не принимают и не отвергают состояния, это Тьюринг неразрешима?» , то он определенно идет бесконечно, то есть он входит в цикл, который можно узнать Тьюрингом.

Answer 3

Вы можете доказать, что в целом

DECIDER_tm = { <M> : TM M is a decider } is undecidable. 

Доказать от противного. Предположим, что он разрешима и пусть R будет определяющим для DECIDER_tm.

Построить S определитель для HALT_tm с использованием R в качестве подпрограммы.

S = on input <M,w> 
1. construct M_w = " on input x" 
    run M on w 
    if M accepts accept. if M rejects reject. 
2. Run R on M_w 
3. If R accept => accept, if R rejects => reject. 

Обратите внимание, что, если M принимает или отклоняет w, M_w останавливается на всех входных, так R принимает M_w это решающий. Если M петли на w, M_w петли на всех входах, R отклоняет M_w.

Мы создали решение для HALT_tm, так как знаем HALT_tm неразделимо наше предположение было неправильным =>DECIDER_tm неразрешимо.