0
4.7kviews
Short Note on Halting Problem
4
161views

The Halting Problem is a special kind of a problem wherein a machine is proved to be undecidable in its behaviour at one point where its composition is changed.

For this, we assume a universal machine for this example and a couple of simpler machines

We consider two simple machine, one(A) which performs addition of two numbers, and another(B) that converts a number from decimal to binary

Machine A cannot execute the output of machine B, neither can machine B execute machine A‟s output.

Now, we have a machine D which executes any machine‟s (here, A or B) output taking that machine‟s blueprint and that machine‟s individual input set as the input.

So, machine D will execute machine A‟s output on gaining machine A‟s blueprint and so is the case for machine B.

Now, we construct a universal machine U that has machine D(to identify the machine to be executed) and a negator machine N(to reverse the output)

If we give machine B‟s blueprint and machine A‟s input set to U, we should be getting an error, which doesn‟t happen as the negator reverses the „false‟ output to „true‟.

If we give machine B‟s blueprint and machine B‟s input set to U, we should be getting the correct, which doesn‟t happen as the negator reverses the „true‟ output to „false‟.

This problem of undecidability is often what is termed as the Halting Problem.