We can prove this by contradiction as follows =>
Consider a machine A which does arithmetic operations and always halts and prints the right answer, but when we feed this machine with the input of macine B, it stucks (Loops forever).
Consider a machine B which plays checkers game and prints the right ouput, but when we feed this machine with the input of machine A,it then stucks.
Now, consider a very smart machine H, which simulates machine A and B with their inputs.
Now, we take the cases :-->
A). It simulates taking machine A along with arithmetic operations, it halts and says not stuck.
B). It simulates taking machine A along with machine B input, it halts and says stuck.
C). It simulates taking machine B along with checker inputs, it halts and says not stuck.
D). It simulates taking machine B along with machine A inputs, it halts and says stuck .
Now, we can say that machine H is a very smart machine which always halts and gives the output. H is here is actually a decider.
But, can a machine like this exist in real world, does it have existence in our world ?
Now, we are going to prove, that this machine existence is impossible . How ?
Consider a machine X which consists of three machines :-->
1). D(Duplicate) - Making 1 copy of whatever is feed into it .
2). H - Our magic machine which is very smart .
3). N(Negation) - Which negates whatever the input is given to it and gives the output .
Ex :- Take a case when we provide machine X with its own description, suppose it stucks (Loops forever).
Now, its time to test how machine X works .
A). Provide the machine X with input of its own description .
B). It goes inside and watches machine D and D takes it as input and Makes a copy of it .So, now there are 2 copies, one is original and other is duplicate copy .
C). These two copies now move forward and encounter H, our smart machine which can do anything . It takes the 2 copies as input and we took this case as example above--> "(Take a case when we provide machine X with its own description, suppose it stucks (Loops forever)."
D). Hence, Machine H prints stuck and this output moves forward .
E). Now, this encounters Machine N, which negates the input and hence, prints Not stuck .
Now, we actually took a case ->
"(Take a case when we provide machine X with its own description, and suppose it stucks (Loops forever)."
But, now we see it does not stuck . Hence, it is comtradicting itself.
Now, take this case ->
"(Take a case when we provide machine X with its own description, and suppose it does not stucks ."
But again, we see that machine X is stuck and hence again contradicting itself .
Hence, No such machine X can really exist .
and similarly, No such machine H can exist .
Hence, Halting problem is undecidable .
