Question

1. Can you (theoretically) solve the halting problem for a physical computer? (Note that it does not have to be practically solvable, it just needs to be solvable in a finite amount of time.)

Answer 1

The Halting Problem asks whether a computer program will stop after some time, or whether it will keep running forever.

Even if (theoretically) we have all the tools to store and count numbers of magnitudes approaching Infinity, we cannot Determine what is the upper limit (unless you specify the upper limit). It will be infinity, and you cannot count infinity. Infinite values cannot be counted, solved or even visualised in finite time.

For example, theoretically, you have infinite time and resources to run your computer with the internet forever. If you repeatedly keep on searching for a webpage which does not exist. You type the URL, you search it, you find no results, you again type the URL, search it, you find no results. You keep doing this forever. You are in an infinite loop, you can't stop unless your mind tells you "There is no use to search any further". Computers have upper limits for dealing with an infinite loop, it will Halt after running a certain number of times. If you remove this upper limit, theoretically your computer will run forever and it will not be able to solve the problem.

There isn't, and never will be, any computer program that can solve the Halting Problem.

The brilliant mathematician Alan Turing also proved that it's impossible for a computer program to solve the Halting Problem.