Computers Cannot Decide Everything: The Halting Problem

[@MadComputerScientist1]

kzbin.info/www/bejne/o5LGfpKDqbiSrZY Here's Computerphile explaining the same thing. They might do a better job. www.scientificamerican.com/article/why-is-turings-halting-pr/ Scientific American explaining why the Halting Problem is Unsolvable

[@TheTwick]

Is do loop that has no resolution (infinite) an example of a non-halting problem? And what are other problems that have no halting?

[@MadComputerScientist1]

There is one caveat here that should be mentioned. A progammer with enough experience can detect that certain conditions might cause infinite loops, which means they can probably figure out a way to determine a few conditions under which a program will not halt without user interventon. A good example is this old Basic program 10 Print ""Hello, World!" 20 GOTO 10 This creates an infinite loop that will repeat indefinitely, another example is: i = 0 x = 1 while i < 1 x *= 2 Because you never increment i, the loop will never terminate.

[@TheEDFLegacy]

The KZbin algorithm has blessed you today! Subscribed, hope it helps!

[@MadComputerScientist1]

Welcome aboard!

[@PhrontDoor]

The thing is, it's not just that computers can't solve this -- nobody and nothing can solve that problem.

[@orion9590]

Hey, I think that saying "A machine's behavior can't be decided if it interacts with the environment, without knowing the environment" is much easier to say than that example. Wait I was wrong? : I think you only need more time compared to what you are running to determine if a code is running for infinity which can be solved by the program treating the other codes as input, not actually running them for infinity

[@MadComputerScientist1]

This wouldn't make sense in context. The point is the machine running the program that doesn't halt will continue on indefinitely. The only way machine B can determine this is if it has infinite time to run the code. Machine B didn't have infinite time to make this decision, and therefore should not be able to tell if Machine A will not halt. It should take Machine B the same time it takes Machine A to run the program. Thus, we have a logical contradiction. I'm not sure how the environment is relevant. Are you using the term in a non-standard way?

[@orion9590]

@@MadComputerScientist1 Recognizing that something is going to go on for infinity does not take forever, if it is finite in size. I did assume that the machine is finite in size. and as such after a finite amount of time it would halt.

[@MadComputerScientist1]

@@orion9590 It does not take an infinite amount of time to realize something will go on indefinitely, without end? While there are edge cases where this is possible, it is not possible in all cases. The final comment shows that you do not understand what a Turing Machine is. The Turing Machine is a hypothetical construct. In the original formulation it has an infinite tape. In the modern formulation, it has infinite memory. Universal Turing Machine: people.cs.uchicago.edu/~simon/OLD/COURSES/CS311/UTM.pdf Further, please read the pinned comment for further information about the Halting Problem.

[@orion9590]

​@@MadComputerScientist1 If I halt, run again. Will this program loop or halt? is probably what you all have been trying to say, just in fancy terms(?).

[@MadComputerScientist1]

@@orion9590 No. The halting problem and the proof that not all things are decidable rests in the logical contradiction I described. Universal Turing Machine A runs the program. Universal Turing Machine B runs a program to tell if Machine A will halt. If Machine A doesn't halt but Machine B determines that it won't halt, how did Machine B determine this without going through the same steps as Universal Turing Machine A? It couldn't have, and as Machine A has not halted yet, Machine B shouldn't have been able to determine this. Please follow the links.I have provided for you here and in the pinned comments.

[@50srefugee]

Is consciousness a computable process? Can it be executed on a Turing machine at all?

[@MadComputerScientist1]

This is something computer scientists are not concerned with. Computer scientists don't even bother much with the Turing Test any more, as most AIs are designed to accomplish a specific task. As much as I'd rather not do this, here is the Stanford Encylopedia of Philosophy's definition of consciousness. plato.stanford.edu/entries/consciousness/ Personally, I would say if we can create a computer or robot that acts in every way as if it were conscious, whether or not it is truly conscious does not matter. We will interact with it and treat it as such.

[@KarmaPeny]

Alan Turing's 1936 paper does not address the halting problem. There is no evidence that Turing ever even talked about halting in his lifetime. The term "halting problem" was first coined in 1958 by mathematician Martin Davis, 4 years after Turing's death. It was retrospectively attributed to Turing (rather dubiously in my opinion) on the basis that Turing's first proof in his 1936 paper was supposedly so similar in its nature that it was considered to be equivalent. Turing was very clear that the subject of his paper was ostensibly the computable real numbers. He explained how each natural number in turn could be converted to a computing machine. Then a decider program D could examine that machine and say whether or not it would effectively represent a real number by endlessly printing a mixture of the symbols '0' and '1'. If it would print these symbols endlessly then he (rather confusingly in my opinion) classified these machines as being "circle-free". I can appreciate how a reader might think that the paper is concerned with halting and looping. It involves a decision problem and he uses the expressions "circular" and "circle-free". Turing also loosely describes an algorithm (to compute a 'diagonal sequence') performed by a machine he calls H. However, it appears to me that H is just the next available letter; it does not have any meaning related to 'halting'. Machine H contains within it the decision-machine D. However, Turing was actually addressing the challenges made by the German mathematician David Hilbert. The concept of a Turing machine was invented for the purpose of examining the claims about real numbers. It followed on from Cantor's claims about the uncountability of the real numbers first published in 1874, Jules Richard's paradox of 1905, and Emile Borel's concept of 'computable real number' in 1912.

[@MadComputerScientist1]

Thanks for the correction. I wish I could pin more than one comment. I do not remember which source I consulted, but it appears that this journal article addresses the issue: www.sciencedirect.com/science/article/pii/S235222082100050X#:~:text=The%20halting%20problem%20is%20a,1958%20book%20by%20Martin%20Davis.