Theory 3 - Reduction Formally, Rice’s Theorem and the Church Turing Thesis PDF

Preview

Summary

Reduction Formally, Rice’s Theorem and the Church Turing Thesis...

Description

Theory 3 (THE3) Module Reduction Formally, Rice’s Theorem and the Church Turing Thesis Autumn Term 2021

Reducing languages and decision problems: 

Let L1, L2 ⊆ ∑* be language L1 is reducible to L2 if there is a computable total function f: ∑* -> ∑* such that for all x ∈ ∑*



Given decision problems P1, P2 we say that P1 is reducible to P2 if Y(P1) is reducible to Y(P2) Reducing L1 to L2



Example:

Example: reducing SAP to MP: 

To reduce the self-accepting problem (SAP) to the membership problem (MP), consider the sets of encoded yes-instances.

Theorem: 

Proof:

Let L1 and L2 be languages such that L1 is reducible to L2 1. If L2 is decidable, then L1 is decidable 2. If L2 is semi decidable, then L1 is semi decidable

1. Let f be the function reducing L1 to L2, F be a TM computing f and M2 be a TM deciding L2. Then a Tm M1 that decides L1 works as follows on input x M1 runs F on x and then runs M2 on F’s output f(x) 2. As in (1) where M2 are M1 are not necessarily halting TMs that accept L2 and L1 respectively. Language properties of Turing Machines:  

 

A property p of Turing machines is a language property if for every TM M having property and every TM M’ with L(M) = L(M’) M’ has property P Examples

A language property P of Turing machines is trivial if every TM has property P or no TM has property P. For example the properties of L(M) is semidecidability and L(M) is not semidecidability are trivial Examples

Rice’s theorem:  



Every nontrivial language property of Turing machines is undecidable. That is, for each such peoperty P, the following problem is undecidable. Property-p problem (PPP) o Input turing machine M o Qurstion – does M have property P? Proof o We show that the Accept- ∧ problem ( ∧ - ∧ ) is reducible either to ´ this is sufficient because PPP is decidble if PPP or to its complement ppp ´ is decidable and only if ppp





o Let Mø be a TM which rejects every input If Mø does not have property P, then we reduce ∧ - ∧ to PPP, otherwise we reduce ∧ - ∧ to ppp ´ Case 1: o Mø does not have property P. We construct a reduction ∧ - ∧ to PPP. Let M be a TM, an input ∧ - ∧ , we assume w.l.o.g. that M cannot crash at the start of the tape. We modify M to a TM M ∧ which operates as followed: M ∧ first moves its tape head to the first block after the input string and runs M as if it s input was ∧ . If M rejects ∧ then M ∧ rejects its input. If M loops on ∧ then M ∧ loops on its input. If M accepts ∧ then M ∧ erases the tape contents to the right of the original input, moves the tape head back to the first square, and executes on its original input a TM Mp that has property P. (Mp exists because P is nontrivial)  If M accepts ∧ then L(M ∧ ) = L(Mp). Hence because P is a language property, M ∧ has property P  If M does not accept ∧ because it rejects or loops then L(M ∧ ) = ø hence L(M ∧ ) = L(Mø). Since P is a language property, M ∧ does not have property P either. Case 2: ´ o Mø has property P. We construct a reduction of ∧ - ∧ to ppp analogously to Case 1, replacing Mp with a machine M ´p that does not have property P. M ´p exists because P is nontrivial  If M accept ∧ then L(M ∧ ) = L(Mø). Since P is a language property and Mø has property P. M ∧ has property P

Decidable problems about context free grammars:

The church-Turing thesis: 

Every effective procedure can be carried out by a Turing machine



Variants o Every algorithm can be carried out by a Turing machine o Every partial function computable by an effective procedure is Turingcomputable o Every decision problem solvable by an effective procedure is decidable....