The limits of computation, a non-Turing machine, the Halting problem and quantum mechanics

Question 1) the limits of computation, i.e., what problems can or can’t be computed?

Any decidable problems are solved by a Turing machine will always require only a finite amount of memory. Also, every function that can be physically computed can be computed by a Turing machine. Classical computability theory originated with Godel, Church, and Turing in the 1930’s, and included a wide spectrum topics. What problems cannot be computed? The answer is the halting problem. Before Kurt Godel’s Incompleteness Theorems were published, David Hilbert believed that all of mathematics follows from a correctly chosen finite system of axioms and that some such axiom system is provably consistent through some means such as the epsilon calculus. However, his idea was wrong. According to Godel’s Incompleteness Theorems, there is statement sin antithetic that cannot be proven or disproved just as there is no Turing Machine that will determine whether a program with input data will ever halt. Alan Turing proved that a general algorithm to solve the Halting problem for all possible program input pairs cannot exist. Therefore, it cannot be computed.

Question 2) it is impossible to build a physical machine that will solve non-Turing computable problem, or will solve an interactable problem in polynomial time

For example, a non-Turing computable problem is the Halting problem. The Halting problem is undecidable that there is no computable function that correctly determines which programs halt and which ones do not. Even if there is no algorithm that solves the problem in a finite amount of time, the problem is undecidable. According to Kurt Godel, he devise a system that’s satisfactorily powerful and well-behaved to encompass mathematical reasoning that system will necessarily contain a statement that we could never prove is true, even though it is true. In addition, Alan Turing showed that there must exist undeciable problems, questions for which there is no definable solution.

Question 3) what are the major differences between the Halting Problem and problems that are believe to be intractable? Why do people think quantum mechanics may help us solve the letter but not the former?

a) First of all, the Halting problem is undeciable. The Halting problem is that given a program and inputs for it, decide whether it will run forever or will eventually stop. Also, it is a decision problem. The 3SAT, non-determistic polynomial complete problem, is also a decision problem. Also, NP-complete problems are computable. If NP-complete problem may spend amount of time to compute, it will get an output either Yes or No. However, the Halting problem will immediately enter an infinitely loop; otherwise, halt will return immediately. In other word, we don’t know its final output either Yes or No.

b) Quantum mechanics may help us to require a small amount of time to compute for NP-complete problem, such a hacking problem. However, the Halting problem is undeciable. Even if the spacetime is reduced, it doesn’t help to solve the Halting problem.