CODEWITHSUNDEEP
computation-theoryturing-machinesdecidable
Garrick
Garrick

Reputation: 689

what is exactly the halting in turing machines ?

I am new to decidability. I read halting problem of halting problem but didn't get anything what it is actually implying. I am already screwed up with the explaination.

Can anyone provide me any sound explaination or atleast some details, it would be of much help ?

Upvotes: 1

Views: 1705

Answers (1)

Patrick87
Patrick87

Reputation: 28302

You can think of a Turing machine as a sort of theoretical computer that can execute programs. A program for a Turing machine consists of a set of states and transitions between these states. Programs running on Turing machines have access to a single input source, called the tape, which has some string (possibly empty) the program can process. All programs for Turing machines either return true (halt-accept), return false (halt-reject), or fail to ever return anything at all - while (true) ; return true;. Depending on your definition it may also be possible for the machine to throw an exception (crash); but typically crashing is thought of as something like try { /*crash*/ } catch (Exception) { return false; } so that crashing means halt-reject.

The halting problem, then, is whether you can write a program for a Turing machine, whose input is another program for a Turing machine and some string of input, which returns true or false (halt-accepts or halt-rejects) if the program it has been given halts on the input provided and returns false otherwise (i.e., if the program never halts).

It turns out the answer is that no such general program exists for Turing machines. Suppose one did exist, M. Given inputs m and i it accepts if m halts on i and rejects otherwise. We can make another program specifically designed to fool M:

N(i)
1. if M(N, i) then loop forever;
2. otherwise return true

Now continue whether M works on N:

  1. Suppose M says that N halts on input i. Then N will loop forever, and M will have been wrong.

  2. Suppose M says that N loops forever on input i. Then N will return true and halt, so M will have been wrong.

In either case, M comes up with the wrong answer for our N, and since we made no assumptions about M other than that it exists and solves the halting problem, we may safely conclude that no machine that solves the halting problem exists.

(M may be passed into the program N as input if it is preferred not to reference M directly).

Upvotes: 3

Related Questions