Nice hyperbolic tesselation

He didn't break it, he didn't even address the problem as Turing did. The fact that you can asses if a program will halt or not was never disputed. This video briefly touches on one of the important elements of the halting program and ignores the other one. In his theory, he briefly mentions the Turing machine. This "computer" (computers weren't even invented yet) has an infinite amount of memory and time to perform any program. So you can never test out each and every memory state as was done with this simple computer. But let's say you have some program (people these days would probably call it an AI to be modern) that can analyze a program's code and, without running it, can decide if a program will halt or run forever. If the code halts, it will execute that code and if the code will run forever, it will stop the code from running. And now comes the part of the halting problem that wasn't covered: what will happen if you let that program analyze itself? Since we do not have such a program on this simple computer and since this computer is also not a Turing machine, you cannot say anything about the halting problem.

Something to add to what Hans said... If you could say whether program halts or not, then you would know *a lot!* Example, imagine programming computer to find proof that Collatz conjecture is true. If it is impossible, then it would not halt and vice versa. That alone suggest, solution for halting problem is too good to be true.

I didn't actually break it, he just constrained the scope of search. The halting problem is decidable in a specific context.

The point of Turing's proof to the halting problem, was that it showed that there exist things that are not computable. It was part of an exploration of the limits of mathematics.

Yeah, and It not even useful to apply on modern computers, se how just 4 bytes created an absurd amount of combinations. My desktop has 64GB of RAM, it has more states than atoms in the universe. And some states are even dependent on the temperature and randomness, its practically impossible to know if it will halt. But I know a way it always halt, pull the power cord.

@@monad_tcp Power cord pull not necessary! Eventually the computer will fall into the sun and halt.

It's not a proof - it's a restatement of the question that avoids the hard part.

Instead of removing the infinite memory, just add infinite CPU, so if it runs forever then it'll finish by lunch. This method even works fine with existing CPUs, when combined with the event horizon of any standard black hole emitting sufficient Hawking radiation

@@alakani Oh, good idea! The infinite tape length of a TM would be countably infinite, but the cycles per second of an infinitely speedy machine would be uncountable I think, because the time per cycle could be any real value. So an infinite speed TM could solve infinitely many halting problems in infinitesimal time. Edit: this is wrong, its still countable.

Elaborate on what the 2nd law of Thermodynamics has to do with any computer programs halting

@@crateer Eventually, due to the heat death of the universe, it will be impossible for any sort of computing machine to continue running no matter when we started it. And thermodynamics might imply that the heat death of the universe is inevitable. Its just a joke.

@@EDoyl You are forgetting the Poincare recurrence time.

​@@ozzymandius666 The Pointcaré reccurence theorem only applies to conservative systems. I know physicists love to ignore friction, but this is the real world

What's even funnier is that I had a bug in my simulator, so the number in the video is wrong 😱

@@simrob Hm, that sounds like a challenge! [edited to add] Ah, there is even a leaderboard.

Turing getting a taste of his own medicine, so to speak :)

@@simrob The halting problem, programming edition. Will a program stand the test of time (halt), or will there be an endless cycle of bug fixes?

@@simrob what's the actual number?

That's 4 billion combinations to check, try two bytes.

@@davidjohnston4240 That is 65,536 possibilities, try one byte.

@@ducksonplays4190 4 bytes = 8*4 bits = 32 bits = 2^32 combinations which is roughly 4 billion.

@@davidjohnston4240 No, I was doing two bytes since you said "try two bytes."

​@@ducksonplays4190That is 256 configurations to test, try a nibble

Apparently it’s somebody writing for the same conference Tom does

I love applying physics to abstract math problems

Well I meant Fundamental Theorem of Arithmetic, so we can safely say you’ve disproved my attentiveness

@@myrus5722 logician bros... we lost

Had to rewatch the video to understand what you were talking about, found out, lolled. Congrats on discovering an actual mathematical flaw with my otherwise mathematically impeccable video. Now I've got to invent a new kind of floating point arithmetic where that's actually computationally correct, I guess, that seems much more practical than admitting I should have used ≅

@@simrobCan’t wait to see the results! Any plans for Sigbovic 2024?

halt by manual interruption out of frustration or interruption by lack of power.

Did you recently watch a video by suckerpinch? That's how i got to this place. Idk how the algorithm works. But some user(s) with similar tastes may have gone down a rabbit hole with some videos you've recently watched + this one, and the alg wants to keep you in a rabbit hole, on the platform, so its trying to get you down the same rabbit hole?

@@ac4740 Same, I recently binged his videos as well and got this recommended.

@@THB_DX ya me too

the small creators being recommended are welcome, imo

checks out

Something can be a stupid April Fool's video and also a pleasantly informative exploration of the Halting Problem! Glad you liked it, though!

I like the point you're making here! If you read the abstract of the project's writeup, it specifies that this is an argument that works for a CORRECTLY OPERATING physical computer. What I mean by that is that the argument only works if your computer only enters "correct states," so that you can simulate all of its behavior faithfully. Building a breadboard computer gives you very visceral experiences in understanding that systems can end up in states outside the scope of their design. It was actually quite a lot of work to get the computer to operate correctly for this video, and then it promptly broke and I haven't yet bought an oscilloscope to figure out why the memory write signal isn't triggering anymore.

If your program has no jumps, the program counter on the 4-bit-memory-version will go 0->1->2->3->0->1->2->3... The rules are described in more detail in the paper.

@@simrob thanks, edited this, I figured it out I think, I'm going to test my program and see how far I come :) It is taking a wee while to get through all three-bytes-and-a-NOP now, time to parallelize it and make it first try to reproduce the 4-byte results you have and then doing a monte-carlo / fully randomized style run I guess until I think of something more clever... exhaustive search of 8 bytes is out of reach even on my Ryzen 7 of course.

@@simrob Seems like I have a subtle bug still in my simulation, is there a way of contacting you outside of KZfaq comments? You can reach me at merijn.vogel @gmail.com (without the space of course) if you'd like. [edit] FIXED a suble bug in calculating the carry for subtraction. You're still very welcome to contact me!

You're correct, of course: the argument I make here only works for deterministic algorithms running on correctly operating physical computers.

...so if you're going with a practical answer rather than a theoretical one - then you have to consider the number of possible states your machine could be in...that would be at least two-to-the-power of the number of bits in RAM...right? OK - so for (say) an Arduino Uno - with VERY modest 2kbytes of RAM - 16k bits. that's 2^16,384 possible states. If you could compare every state to every previous state once a nanosecond before the heat-death of the universe (10^106 years - 10^122 nanoseconds - roughly 2^400) - you still wouldn't have checked more than a microscopic fraction of possible states that our humble arduino could reach. So even with practical amounts of memory, the time required is crazily, impossibly, long. To all intents and purposes - the amount of RAM in ANY modern computer might as well be infinite.

@@SteveBakerIsHere You're still assuming arbitrary programs. Not all states need to be checked.

​@@NielMalan I'm not "assuming" that - I'm telling you what the halting problem actually *IS*. The halting problem doesn't say that NO program can be detected as being halting or infinite looping. Obviously there are classes of program (eg those with no loops, jumps or recursion) that obviously halt and are easily detectable as halting. There are other classes of program (such as those with "while(true) ;" at line 1) that obviously loop forever and can easily be detected as such. The proof of the halting problem says that you cannot decide the question for EVERY POSSIBLE PROGRAM. So what you're saying it still bullshit. You very clearly don't understand what The Halting Problem is - and as a result you're talking complete nonsense...and worse - claiming that a proven mathematical principle is false...which is **EVIL**. You should read en.wikipedia.org/wiki/Halting_problem - and follow that up with en.wikipedia.org/wiki/Entscheidungsproblem - which is the deeper question which the proof of the Halting Problem also answers...which in turn is why Alan Turing invented the Turing Machine - and why the Halting Problem is so important to mathematics in general.

@@SteveBakerIsHere I don't claim that the Halting Problem is false. I am pointing out that the Halting Problem does not apply to practical computers that do not run arbitrary programs with arbitrary inputs. The Wikipedia article on the Halting Problem mentions two approches to writing real programs that can be guaranteed to halt: either using a specific programming style, or using a non-Turing-complete language.

@@NielMalan The only reason it doesn't (strictly) apply to practical computers is because they don't have infinite memory. However even the simplest computers (and Arduino, for example) have far more possible memory states than you could compare to determine whether it'll halt or not. So the practical answer for a practical computer is exactly the same as the theoretical answer for a theoretical computer. You STILL can't compare memory states fast enough to see a repeat within the life of the universe. So it doesn't matter whether you appeal to practical computers or theoretical one the outcome is exactly the same. All languages that are equivalent to a turning engine are vulnerable to the same problem - and all actual programming languages are equivalent to a turning machine (Note: the Church-Turing thesis). Yes - you can adopt programming styles that can be proven to halt (or to not halt) - but nobody is arguing that you can't prove that SOME programs halt or SOME programs don't halt. Sure you can narrow the claim down to the point where it doesn't apply...but what you wind up with isn't a useful statement of anything. My objection is to the title of this video - which is ABSOLUTELY false...in both theoretical and practical terms.

The important point is that computers are deterministic and that you need to look at the entire state of it. That includes all of the memory, including the program, program counter etc. So for the computer to be in the same state, it has to be at the exact same instruction in the exact same program with the exact same data. This should always produce the same result, or your computer is broken.

No.

hey, what's your avatar of?

@@mothtolias anthropomorphic mouse :D

@@Iamveryconfusedabout who's the artist?

@@mothtolias I commissioned my friend dan :D, I think his Twitter is @danvirile

@@Iamveryconfusedabout oh neat, that's awesome! they've done a great job

I filmed the sucker with a doc cam and do not know what I am doing. ¯\_(ツ)_/¯

No.

Please watch video before facepalming. The halting problem proof relies on infinite memory size. If you don't assume that, halting is computable. Either a state has been reached twice indicating an infinite loop or the halt instruction gets reached in some way.

the diagonalization approach assumes the answer MUST be limited to either true or false. once you loosen that restriction, the proof no longer applies. for instance if the halting_checker program identified which inputs would result in halting.

@@judgeomega Well that's the point. The halting problem asks "Will it halt?" not "Might it maybe halt?" The latter question can be answered very easily...but that's not what the halting problem is all about. It's about decidability - the Entscheidungsproblem. What you're going on about isn't that.

@@SteveBakerIsHere iv thought long and hard on this before, and although what you say is commonly accepted as the end all be all of truth... my examinations have led me to believe that space and time itself are fundamental to processing in a manner which current math does not yet recognize. infinite input, certain programs/inputs with subtle time sensitive components, and recursion require/produce more information than a single bit can hold.