È corretto dire che l è ri se posso mappare la riduzione da lh a l?

Question

Mi sembra di non capire correttamente quali riduzioni significa per le lingue.

Ad esempio, diciamo che c'è una lingua chiamata LM.

Voglio vedere se LM è ricorsivo o no, per farlo, dico di dire che trovi una riduzione dal problema di L-halting a lm.

E presumo che LM sia ricorsivo, quindi mostro che allora il problema a L-halting è anche ricorsivo, che ovviamente è falso quindi lm non è ricorsivo.

Ma posso dire che lm è re perché ho trovato un modo per ridurre lh a lm? Se no come posso mostrare che lm è re?

Answer 1

Cancella le cose un po ', poiché ci sono molte definizioni equivalenti / simili che potrebbero portare a incomprensioni.

.

• Puoi mostrare che una lingua $ l $ è ricorsivo costruendo una funzione ricorsiva $ \ chi_l $ (o una macchina di turing o qualsiasi altro modello di calcolo equivalente) che lo decide, cioè $$ \ CHI_L (X)=Begin {casi} 1 & \ quad; x \ in l \\ 0 & \ quad; \ testo {otw}. \ end {casi} $$ Si noti che $ \ CHI_L $ deve essere definito per tutti gli ingressi.

• Puoi mostrare una lingua $ l $ non è ricorsiva, trovando una "riduzione di turing" da un non -Ninquente lingua. Questo è probabilmente ciò che intendi per riduzione, ed è definito come segue:

  .

  Diciamo che una lingua $ A $ è di turing-riducibile a una lingua $ B $ , scritto $ a \ le_t B $ , se possiamo costruire una funzione ricorsiva (o macchina di turing) che decide $ A $ < / span> Assunzione che vi è tale funzione per $ B $ .

  Come vedi per definizione, tenue riduzione in qualche modo "Trasferisce la ricorsività" da $ B $ a $ A $ .

  .

  per qualsiasi class class="math-contenitore"> $ a $ e $ B $ tale che $ A \ Leq_t B $ , se $ B $ è ricorsiva, quindi è $ a $ .

  Quindi se sappiamo già che qualche class class="container di matematica"> $ A $ non è ricorsiva, quindi trovando una riduzione $ a \ leq_t b $ per qualsiasi classe $ B $ lo rende anche non ricorsivo.

• Puoi mostrare che una lingua $ l $ è re, da costruzioni una funzione ricorsiva $ \ VARPHI_L $ (o macchina di Turing) che $ DOM (\ VARPHI_L)= L $ (o fermi su / accettalo), per esempio $$ \ Varphi_l (x)=Begin {casi} 1 & \ quad; x \ in l \\ \ uprerow & \ quad; \ testo {otw.} \ end {casi} $$

  Dove $ \ OPPROW $ significa "non definito" (o "non si fermano"). Ci sono altre definizioni di re-ness, come il suo omonimo "enumerabilità", che puoi facilmente osservare che sono equivalenti a questo.

• Ma nel mostrare una lingua $ l $ non è ri, la riduzione non aiuta, poiché non è necessariamente trasferimento re-ness. Ad esempio, osservare quella classe $ \ overline {l_ {halt}} \ leq_t l_ {halt} $ (anzi ogni linguaggio turing-riducibile al suo complemento e viceversa), Ma sappiamo che $ l_ {halt} $ è re, mentre $ \ overline {l_ {halt}} $ non è.

  Ma ci sono altri tipi di riduzione più forte che trasferiscono re-ness. Una di queste riduzioni è chiamata "Molti-One Reidicibility":

  .

  Diciamo che una lingua $ A $ è molti-one-riducibile a una lingua $ B $ , scritta $ a \ leq_m B $ , se c'è una funzione ricorsiva totale $ f $ tale per qualsiasi ingresso $ x $ $$ x \ in a \ IFF f (x) \ in B $$

  Questa è una riduzione più forte nel senso che $ a \ leq_m B $ implica $ A \ leq_t B $ (e non necessariamente viceversa). Quindi, come la riduzione di Turing, trasferisce la ricorsività. Abbiamo anche

  .

  per qualsiasi class class="math-contenitore"> $ a $ e $ B $ tale che $ A \ leq_m B $ , se $ B $ è re, quindi è $ a $ .

  Per vedere come è vero, basta prendere $ \ varphi_a (x)=varphi_b (f (x)) $ .

  Da qui il metodo corretto per mostrare una lingua $ B $ non è re, è trovare una riduzione di una riduzione di molti $ A \ leq_m B $ per alcuni linguaggi non re $ a $ . Si noti che l'esempio sopra non funziona qui, perché $ \ overline {l_ {halt}} \ nleq_m l_ {halt} $ .

Per ulteriori letture, vedere

l="Nofollow NoreFerrer"> Teoria del calcolo per s.Barry Cooper Pt.Io, ch.7.