Report

Theory of Computing Lecture 20 MAS 714 Hartmut Klauck Decidability • Definition: A language is decidable if there is a TM that accepts all words in the language and rejects all words not in the language • In particular it always halts in finite time • For a Turing machine M the language accepted by M is the set of x on which M accepts (denoted by LM) Example • U={<M>,x: M accepts x} – Universal Language (inputs acc. by the universal TM) • U is not decidable: HALT· U – Note: decider must be correct and halt on all inputs • Reduction: Map <M>,x to <N>,x – where N is the machine that simulates M, and if M halts, then N accepts (N never rejects) • <M>,x2 HALT, <N>,x2 U Decidability • The complement of L is the set of strings that is not in L (over the same alphabet) • Observation: L is decidable if and only if C(L) is decidable – simply switch acceptance with rejecting • Corollary: If L is not decidable then C(L) is also not decidable • Example: EMPTY={<M>: LM=;} is not decidable – Note this is not exactly the complement of NEMPTY, but the complement minus a computable set: {x: x is not a TM encoding} Equivalence • EQ={<M>,<N>: LM =LN} • • • • Theorem: EQ is not decidable Reduction from EMPTY Fix some TM N that never accepts Reduction maps <M> to <M>,<N> Closure • If L is decidable and S is decidable then – Complement of L is decidable – LÅS is decidable – L[S is decidable • Corollary: – CH={<M>: M halts on no input} is not decidable • CH=C(H)-{x: not encoding a TM} Rice’s Theorem • A (nontrivial) property P of languages is a subset of all languages – such that there is a language (accepted by a TM) with P and a language (accepted by a TM) without P • Theorem: Let L(P)={<M>: LM has property P}, where P is a nontrivial property – Then: L(P) is not decidable • Example: {<M>: fM can be computed in polynomial time} – Note: M might not run in polynomial time • Not an example: {<M>: M runs 100 steps on the empty input} Proof [Rice] • We assume that ; does not have property P – Otherwise we use the complement of P • Denote by A some TM such that LA has property P – Must exist since P is not trivial • We show that U· LP • Given <M>, x we construct Mx: – Simulate M on x – If M accepts x then simulate A on the input u to Mx – If M does not accept x go into infinite loop • Now: <M>,x2 U) M accepts x ) Mx accepts u iff A accepts u) Mx behaves like A and L(Mx) has property P • <M>,x not in U) Mx will not halt) L(Mx) is empty, L(Mx) does not have property P Nondeterminism • Consider the set of languages that can be accepted by nondeterministic TM that always halt • As before we can see that these can be simulated by deterministic TM that run in exponentially more time • Corollary: Computability by deterministic and nondeterministic TM is the same as long as the TM must halt • What if the NTM does not need to halt? One-sided decisions • For NP it does not matter if the NTM halts on inputs not in the language, because we have a time upper bound and can stop the machine after that time • If there is no time bound we never know if the machine might still accept • Definition: A language L is recognizable if there is a TM that accepts it (which might never stop on inputs outside of L). Example • Halting problem HALT • Simply simulate M on x • If M halts on x, accept • Clearly: all <M>,x that are in HALT are accepted, all other <M>,x are not accepted • Theorem: HALT is recognizable • Similar: H={<M>: M accepts some x} is recognizable Complements • Theorem: – If L and C(L) are recognizable, then L is decidable • Proof: – There are recognizers M and N for L and C(L) – Idea: simulate both in parallel • Simulate M for a few steps, then N, then M again... – One of them stops: can make the decision – x2 L then M accepts and our machine also accepts – x2 C(L) then N accepts and our machine rejects Complements • Corollary: the following situations are possible: – L and C(L) both decidable – L recognizable but C(L) not recognizable and both not decidable – both L and C(L) not recognizable • Example: HALT is not decidable but recognizable, hence C(HALT) not recognizable Not recognizable • Theorem: Assume L· S . If L is not recognizable then S is not recognizable – Proof: If S is recognizable, we can recognize L by computing the reduction and then using the recognizer for S • Theorem: C(U) is not recognizable • Proof: Enough to show that U is recognizable, since U is not decidable • How? Simulate M on x. Not recognizable • Theorem: EQ is not recognizable – Reduction from C(H)={<M>: M halts on no x} – Given <M> find N: N simulates M and accepts if M halts – Map <M> to <N>, <S>, where S does not accept anything – Then: <M>2 C(H) , N accepts nothing , <N>,<S>2 EQ Not recognizable • Theorem: C(EQ) is not recognizable • Proof: C(EQ)={<M>,<N>: LM LN } Reduction from C(U) N: ignore input, simulate M on x, accept if M accepts S: accept every input Map <M>, x to <N>,<S> If M is in C(U) them M rejects x or never halts. Then N rejects or never halts on every input, then N and S do not accept the same language – If M is not in C(U), then M accepts x, then N accepts everything, then N and S accept the same language – – – – – – Corollary • There are languages such the neither L not C(L) are recognizable Enumerable • Definition: L is enumerable, if there is a Turing machine M that writes all strings in L to a special output tape – M has no input and runs forever • Theorem: L is enumerable iff L is recognizable – Proof: • ): Enumerate L, test each output against x, once x is found, accept Back direction of the proof • Idea: loop over all inputs, and write the accepted ones to the output tape • Problem: TM does not halt • Solution: Dove-Tailing: – – – – Loop over all strings x Loop over all integers i Simulate M on x for i steps. If M accepts, write x to the output tape • Clearly this machine eventually writes all recognized strings to the tape Other problems? • All problems so far concern Turing machines • Any other undecidable problems? • Example: Arithmetic – Given a sentence in Peano arithmetic, can it be proved from the Peano axiom [is it a theorem]? – Undecidable – Decidable: remove multiplication, still hard for doubly exponential time [Presburger arithmetic] Hilbert’s 10th problem • A Diophantine equation is p(x1,…,xn)=0, where p is a polynomial with integer coefficients • Question: Are there integer solutions? • Example: an+bn=c n, are there integer solutions for n>2? – There are none, but this slide is too small for the proof… • Theorem [Matiyasevich ’70]: The problem of solving Diophantine Equations is uncomputable Example: Posts’ correspondence problem • Given two sequences of strings – example: A=[a, ab, bba] and B=[baa, aa, bb] • Can we find a set of indices such that the corresponding strings are the same(concatenated? • Example: 3,2,3,1 – bba ab bba a = bb aa bb baa • Problem is undecidable