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

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


turing-machines
person Frank Joe    schedule 30.10.2016    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Решающее устройство — это машина, которая останавливается на всех входных данных. Не существует общего способа доказать, останавливается ли данная машина на всех входных данных.

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

person Welbog    schedule 31.10.2016
comment
Меня немного смущает бесконечный ввод. Если бесконечный ввод поддерживает изменения машины Тьюринга между двумя состояниями, и оба состояния не принимают и не принимают состояние, является ли эта машина Тьюринга решающим фактором? - person Frank Joe; 01.11.2016
comment
@FrankJoe Нет такой вещи, как бесконечный ввод. Каждый вход должен быть конечным. Кроме того, если TM работает вечно, то это не является решающим фактором. В конечном итоге он должен нажать «Принять» или «Отклонить», а затем прекратить движение (обратите внимание, что НП никогда не продолжит движение после того, как достигнет одного из этих двух состояний по определению). - person Nicholas Pipitone; 05.02.2019

arrow_upward
0
arrow_downward

TM определяет язык L тогда и только тогда, когда 1- строки L переводят M в состояние Accept 2- строки NOT IN L переводят M в состояние Reject

TM M распознает язык L тогда и только тогда, когда 1- строки L переводят M в состояние Accept 2- строки NOT IN L - ЛИБО переводят M в состояние Reject - ИЛИ заставляют M зацикливаться

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

person S_Raj    schedule 05.08.2017
comment
Вероятно, вам нужно отредактировать и перефразировать, чтобы сделать более очевидным, как ваш текст на самом деле отвечает на вопрос. - person Yunnosch; 05.08.2017

arrow_upward
0
arrow_downward

Вы можете доказать в общем, что

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 неразрешимо.

person acagu    schedule 09.08.2017