Halting problem:

• Problem

-   Given a Turing machine T and string z, does T halt on z?

-   Given a program P and input z, does P halt on z?

• Language

-   Halt = {wΣ∈*| w=e(T)e(z) for a Turing machine T halting on z}.

-   Halt = {<T,z>| T is a Turing machine halting on z}.

Halting problem is undecidable:

Proof:

Let Halt = {<T,z>| T is a Turing machine halting on z}. (Guess Halt is in R.E., but not co-R.E.)

• Show SA ≤Halt

(We want a Turing-computable f n f(<T1>)=<T2 ,z> such that

-   T1 accepts e(T1) -> T2 halts on z

-   T1 does not accept e(T1) -> T2 does not halt on z

Then, a possible function is f(<T>) = <T, e(T)> because T accepts e(T) ↔ T stops on e(T).)

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Halting problem in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.