Prova del teorema del riso

Question

Permettere $ P $ essere qualsiasi proprietà non banale del linguaggio di una macchina Turing. Dimostrare che il problema di determinare se la lingua di una determinata TM ha proprietà $ P $ è indecidibile.

Prova: (questo è dal libro di SIPSER).

Supponiamo per il bene della contraddizione che $ P $ è un linguaggio decidabile che soddisfa le proprietà e let $ R_p $ essere la TM che decide $ P $.

Mostriamo come decidere $ A_ {tm} $ usando $ R_p $ costruendo TM $ S $.

Prima let $ T_∅ $ Sii un TM che rifiuta sempre, quindi $ L (t_∅) $ = ∅.

Puoi supporre che $u003CT_∅> notin p $ senza perdita di generalità, perché potresti procedere con $ bar {p} $ invece di $ P $ Se $u003CT_∅> in p $.

Perché $ P $ non è banale, esiste un TM $ T $ insieme a$u003CT> in p $.

Disegno $ S $ decidere $ A_ {tm} $ usando $ R_p $ la capacità di distinguere tra $ T_∅ $ e $ T $.

$ S = $“Su input $u003CM, w> : $

1. Uso $ M $ e $ w $ Per costruire il seguente TM $ M_w $.

   $ M_w $ = “Sull'input $ x: $

   1. Simulare $ M $ Su $ w $. Se si ferma e rifiuta, rifiuta. Se accetta, procedi sul palcoscenico $2$.
   2. Simulare $ T $ Su $ x $. Se accetta, accetta. "

2. Usa tm $ R_p $ per determinare se $u003CM_w> in p $. Se sì, accetta. Se no, rifiuta. "

Tm $ M_w $ simula $ T $ Se $ M $ accetta $ w $. Quindi $ L (m_w) $ è uguale a $ L (t) $ Se $ M $ accetta $ w $ e $∅$ altrimenti.

Domanda: ho difficoltà a capire le ultime righe di questa prova. $ R_p $ è un decisore che decide $ p $. Ci dice che una macchina ha la proprietà $ p $ o no. Quando corriamo $ R_p $ sulla descrizione di $ M_w $ e supponiamo $ M_w $ accetta $ w $ Quindi la lingua di $ M_w $ è uguale alla lingua $ T $ altrimenti $ phi $. Ora non capisco come questo dimostra che il problema di accettazione sia anche risolvibile se decidiamo $ P $. Sono bloccato al suo punto, qualsiasi aiuto sarebbe fantastico.