Are There Problems That Computers Can't Solve?
Dipublikasikan tanggal 10 Mei 2020
All about Hilbert's Decision Problem, Turing's solution, and a machine that vanishes in a puff of logic. MORE BASICS: • The Basics
Written with Sean Elliott SeanMElliott/
Graphics by William Marler wmad.co.uk
Audio mix by Graham Haerther haerther.net/
I'm at tomscott.com
on Twitter at tomscott
on Facebook at tomscott
and on Instagram as tomscottgo
Written with Sean Elliott SeanMElliott/
Graphics by William Marler wmad.co.uk
Audio mix by Graham Haerther haerther.net/
I'm at tomscott.com
on Twitter at tomscott
on Facebook at tomscott
and on Instagram as tomscottgo
10:58
🏆 Kings of Europa League! Sevilla's post-match scenes & trophy lift | UEL 22/23 MomentsbeIN SPORTS Asia
Ditonton 478 rb
Komentar: 5 952
Both my co-author Sean and I are worried that we're oversimplifying here -- but then, this series is called The Basics!
Tom Scott nice video
Sometimes you just have to simplify things, or else, you'll spend days talking about subjects
Are you going to talk more about BASIC
Basic Bro
Keep the complexities basic
When you try to solve a mathematical problem so hard that it turns into a philosophical one.
Gödel's incompleteness meme?
Was this a mathematical problem ? Was a mathematical computer the right tool to use in this instance ?
Mathematical proof is based on philosophy
It's to opposite. The original problem is philosophical: "Is there a chance, even the slightest, that maybe some day far in the future we will have answers to all questions in the universe?" Maths and logic brought the definitive answer: "Nope. We can prove that it's impossible with just the subset of mathematical questions. And the full set of all questions is far larger than that."
Mathematics is actually a branch of philosophy, so... technically every mathematical problem is philosophical.
Fun Fact: you can build a fully functioning Turing machine within the rules of Magic: The Gathering and given a perfect starting hand you can even set it up legally in a tournament game. There’s even a paper on that, for those that are interested.
Could I have the source?
@Kasoy I believe Kyle Hill did the video Fabian is referring too.
@SlovenMalaphor link?
@SlovenMalaphor link?
@SlovenMalaphor Link?
"Any program that you write in any programming language can be converted into something you can run on a Turing machine." So... Another thing you can run doom on?
Well I wouldn't put it past Bethesda to port Skyrim to a Turing machine.
Sent from my Turing machine
But can it run crysis?
@775 Given enough tape, yes, it can
@Jimmy Diaz Can a Turing machine overheat? The answer is no. Can any computer run Crysis without overheating? The answer is also no. Run Crysis on a Turing machine - get another paradox.
As a software engineer, I can say that your simplification is reasonably adequate :-). BTW, Kurt Goedel basically arrived at a similar conclusion with its two incompleteness theorems. A brilliant work.
Gödel's Incompleteness Theorem also follows this self-referential principle to arrive at paradoxes, but the consequences are even deeper. The fact that it implies that any set of mathematical axioms either produce truths that cannot be proven by those axioms alone, or that they outright contradict themselves, is amazing. Just imagine how many problems we have right now that are worth a million dollar prize, some of them might literally be true, yet have no formal mathematical proof. It makes my head spin.
The big problem that I know of that could be this way is the Riemann Hypothesis. However, if we could prove that the Riemann Hypothesis is unsolvable from the axioms of math, then that means that it is true because if it were false we would have a way of proving it false from the axioms.
And the thing is, the paradox is a deceptively simple "This sentence is a lie." formulation. It almost seems silly that this could tie logic up in knots, but there you have it. The fundamental flaw in formal logic.
@E Fulmer That doesn't mean it's true, it means it can be both.
@Braude Numberphile has a video on Godel's Incompleteness Theorem and they mention implication that the implication that the Riemann Hypothesis is true if it cannot be proved true from the axioms.
Will this code halt or loop? Quantum Computer: *"Yes"*
Actually, that is the solution. This problem IS SOLVABLE as of 2020, when a team of 5 compscis solved the halting problem using quantum entanglement.
@Jamie Lonsdale nice! Do you have a link to the paper, I would love to read it?
@Jamie Lonsdale lmao no
@Γρηγόρης Α I'll have a look when I finish my shift :)
well, actually Quantum Computer: "Yes, No, Yes and No"
Yes. Try to ask my computer why the internet is down.
Surely it can Google the answer.
@T Duke Perry well if you have only one internet access then it's not possiblle to google the answer xD
@AlphaGT r/whooosh
Or just ask the computer to read a captcha.
@Tau hey thanks I haven't got this in a while
I am a computer science engineer and, yes, *I do appreciate your "deliberate semplification".* May all of us be able to explain things like you are. All with that commendable, pervasive sensation of you having actual cognizance of what you are talking about. Happy recent subscriber of yours.
As an Electrical Engineer my take on deliberate/oversimplification. If you cannot explain a concept without using math or hyper technical jargon then you don't understand the concept. Basic example, the Fourier Transform, it is defined with integrals and dummy variables and complex numbers and all this junk that takes at about 1.5 years of college to be able to perform. But what does this painful math actually do, it converts songs from audiofiles to sheet music (assume instrumental only). Obviously this isn't all its good for or even exactly what it does, but the full answer takes litteral years to build up to. A more accurate description is that is converts functions from time domain to frequency domain, but those aren't universal concepts like instrumental only music and sheet music. (I assume everyone is forced to do atleast a little bit of music theory in elementary school)
Tom Scott and James May are the only two people I know who can make topics that don't particularly interest me sound absolutely fascinating.
Even though you’re “oversimplifying” I still have to pay a lot of attention to keep up. The simplification is making the video very accessible to people who cannot code and who doesn’t know much about computers
They really paid Turing back for his help.
Oof. Happy pride month :/
The minds we lost to discrimination of any kind.... sad world.
No good deed goes unpunished.
@Stijn And a lot of it founded in some religious doctrine of one form or another.
@TheKazragore oh no not religion! Imagine blindly accepting a proposition, that certainly doesn't apply to anyone here.
I envy this guy ability to make all this awesome content in just one take
Tom’s way of speaking is always so engaging. You just feel inclined to listen to him and it’s so easy to follow along. Glad this guy decided to become an educator, it’s always a pleasure!
Imagine having him as like a lecturer or teacher. It'd be great
I have a video of him explaining things at my school. (edit) it's the one on my channel
XBC Video Link? Asking for a friend
Well said!
I agree
I'm glad you mentioned that this problem is _mathematically_ impossible to solve. The two other videos I've watched about the halting problem made it sound like it was only impossible for computers specifically, when really it's a logical paradox, impossible for everybody.
exactly a more human friendly representation of this problem would be "if true then false if false then true"
Nice video with a good treatment of the problem. There's always one thing I wish presenters would bring up, and Tom flirted with it. One of the key assumptions in the halting problem is that we're working with an idealized Turing machine, which is related to Hilbert's problem. In the real world no computer is truly a Turing machine because it has finite memory. You can definitely answer the halting problem for a machine with finite memory; you just need a larger machine that is able to simulate the smaller machine. For any given state, the big machine simulates the small machine until the small machine goes back to a state it has already been in (loops forever) or gets to the halt state (halts).
I think perhaps my favorite thing is that everything loops back around to a core truth, no matter who's asking or how- The answer to "Is _x_ limitless?" is always "No, and you pure theory types need to stop asking." Physicists and chemists, mathematicians and engineers, the question never changes and neither does the answer XD
Yet, the paradox does not rely on the machine being infinite. Regardless of how the machine looks like: if it detects a halt, it runs forever, if it detects a run forever, it halts. Feed it to itself and you have the paradox. Does a program like while (user input != "Ctrl+C"){} terminate? Even with just one byte of memory, this is undecidable. Because we do not know if there is a user and if they will somewhen press Ctrl+C. The infinite band of the Turing machine does not EQUAL the internal memory, that's just more of an analogy. Rather it may also contain other information like inputs and time passing depending on how you transform a real-world system into a Turing machine. Interesting is that the problem is not symmetrically undecidable. It is rather easy to prove if there exists a path in a program / model / machine that is terminating. But we cannot prove, that ALL paths will EVENTUALLY terminate. We cannot even determine, whether a "loop" is executed infinitely often or just once or several times before branching to a terminating path. Oh, another nice code example: do { x = randomize(); } while (x != 5) Statistically, this might be likely to terminate. But we cannot be sure, if we have an unlucky run and never hit 5. Moreover the "big machine simulating the small machine" might see the state "x = 4" several times, decide, that there is a loop and decides the program does not terminate but in the next iteration, x is 5 and the program does terminate. Big machine failed.
@Aderendhuelse Well when you're talking about impure programs where you're waiting for input from the user, essentially the answer is almost always that it won't necessarily halt, because the user could just never press anything and the program would go forever. The question of whether the program will halt is essentially a "is it possible for this program to not finish and go indefinitely?" Once you introduce any kind of awaited user input, that almost always becomes the case. As for random numbers, if the randomize function is truly random and capable of producing a 5 result then the program will eventually end. You don't know when it will end (assuming the RNG is totally random), but eventually it will. There's no such thing as an unlucky run, because there's no set time limit where we give up and call the program frozen. Given infinite time, it will eventually end.
@taragnor You could easily modify the function: x = randomize() if x == 5{ loop } else { halt } If the number is truly random there is no way to know if this function will halt or not. Of course there is the issue of whether or not truly random numbers even exist, but the main contradiction is in the halting problem.
"Is 'no' the answer to this question?" Computer dies
Meanwhile Human: "Yesn't"
A computer can be made to recognize that "answer" and "response" aren't synonymous. Hell, any automatic grading system already knows just putting text in the box doesn't mean you put the right answer.
Probably not
It could just answer it in a different language.
Definitely.
Do more videos with Matt. I love the technical difficulties stuff!! I also think it would be a good idea to promote the Matt and Tom channel on this channel more! Had I known about that channel longer ago, I'd have been a long time viewer of it too!
Hilbert, Turing and Gödel lived great lives and impacted much of maths. I recently read a book called The music of the Primes by Marcus de Sautoy with chapters on them. Definitely worth a read.
Socrates: "The next thing Plato says will be false." Plato: "Socrates has spoken truly."
prints " thats deep " * infinitely *
This is hurting my brain.
This doesn't seem paradoxical, please can someone explain? It seem that socrates is just wrong here.... Or plato is wrong theres no loop here
@Anim8D Ideas If socrates is wrong then plato is wrong, which makes socrates correct, etc etc
When two people lie and a third person doesn't understand complicity and deception, then they are truly more stupid than machines.
Love your channel, Tom. Easy to digest, interesting and educational
Love the videos Tom! Hope we can get more and more variety in the content of this series
I'm just curious to know what "vanishing into a puff of logic" would look like. I would love to see someone create a basic version of this paradox (if that is even possible) and see what the compiler does. Will it throw an exception? Will it just not run at all? I am curious.
it's will result to a runtime error (stack overflow)
@Zero Anims would that be equivalent to throwing an exception in C++? I'm not as good with programming languages as I used to be 😅
@Liam Farrell yes for some platform like windows it throws an exception albeit an asynchronous one
@Liam Farrell Yes, specifically the infinitely recursive recalculating of "halts, will not, halts, will not, halts, will not, ..." would overflow the stack and throw an exception
Many coding languages throw an exception if a code runs for too many repetitions, assuming it's an infinite loop. If a language doesn't have that it'll just go on forever until you kill it. But that repetitions check is just arbitrary, it's possible to write a code which will do something 90 quadrillion over and over then do something different.
This channel is a blessing. Such a variety of interesting content.
Would be fun to hear Tom's full lecture series on it
Me: “this is really complicated” Tom: “sorry for massively over-simplifying”
That's literally the best flex for every "nerd" to say lmao
The core of the idea is simple, proof by contradiction that you can always create. But to actually *prove* that that proof works requires a college computer science course. Hence massive oversimplification. The main takeaway is that a "universal computer" *isn't.* Some things are inherently non-computable. Theory of Computation is then the branch of computer science that tries to figure out what those things are and aren't, among other things.
It is massively over-simplifying. There is a reason why there are half-a-semester course on just this particular subject. If you don't want simplify / to gloss over the details, and actually fully understand the details. Then it takes a very long time to explain.
@2d Ninja Computer compute many computations but not all. Smart people compute what computations computers cannot compute.
I've always wondered about a slight variation on this "Halt" computer. How about if we could create a program that would read data and a program and generate one of three outputs. The combination will Halt, the combination will loop, or the combination will generate a contradiction. How would that figure into the decision problem?
This just reminds me of GLaDOS's failed effort to disable Wheatley by telling him "This sentence is false."
Um… true, I’ll go true. Huh, that was easy.
Don't think about it.
same, i was thinking that too lmao
This video really puts into perspective how much of a massive genius Alan Turing was
I'm taking an exam in this next week - not too oversimplified imo :D Bonus fact: There are infinitely more uncomputable decision problems than computable decision problems!
Small technical detail at 1:32: It is possible to determine if a program will loop (do the same thing over and over again) forever. Halting is not solvable because of those programs that keeps on doing new things forever. Small but important detail that can be very hard to put into a 7-8 minute introduction but it is an important detail that I have to mention.
6:11 "Vanishes in a puff of logic" is one of the best Hitchhiker's Guide references. Computers are logic machines at their core. It's an important class in Computer Science programs, because underneath at the most base level chips just send electrons through AND, OR, NOR, etc gates incredibly fast. And that same logic can bubble up into even high level languages.
haha yes I knew I couldn't be the only one to get that reference!
Also a NetHack reference.
42
Also important, various other forms of logic will sift down from very high level language theories and inform the nature of types and programs, so logic ends up being in both directions when it comes to computers.
So that means redstone is technically a computer, because of all those logic gates.
That's interesting, cause people who made modern IDEs (programs for writing new programs) to some extent resolved this problem, they wrote code analyser, that checks every line of code before compiling the program and shows lines that determines infinite loops or something similar. It can't be 100% sure halts new program or not, but it's amazing. One program analyzes other program and finds potential errors in it.
There is a way to stop a loop at least. Run the iteration on a separate thread and use a delagate to pass a bool named something like requestStop with a if statement in the do while block if(!requestStop){}else{break;} it works and keeps the render thread from getting stuck.
Does this change if you use quantum computing? Superposition seems to play into the paradox quite well.
On the issue of an infinite loop, you could code into some base code, possibly the os, to keep track of the past "x" commands or strings of commands, let's say ten, that the computer runs, and checks them. If the computer runs "10>Print "rudeword" 20>goto 10" ten times, it then makes the assumption that it WON'T ever escape the loop and ceases to run that code. It goes to line 30, or just ceases the program and says "Error: inf. loop, lines 10-20". Obviously if a loop would repeat MORE than ten times before escaping, or you end up creating a loop that has a change like printing" "rudeword" Int-X" to print out something slightly different every time then it would circumvent your safeguard, but a basic safeguard can often catch MOST instances, and in meat world problems outside the realm of theory most can be good enough. Plus once you identify that issue you can program in something like "If this variable changes by the same value every time before printing recognize a loop" Which... I only know the basics of coding, but once you know that you can code that and have a buddy try to break it, repeat until it's close enough
That's what I loved about IBM's OS2. Everything ran on a virtual machine. You code in one window and run it in another. If it freezes or goes into a loop, close the window, and start going over your code. I would laugh at my classmates who complained about their C code freezing on their Windows machines and they would lose an hour's work.
Wow I had no idea...that's such an amazing concept
This actually ended up being an extremely important discovery, as ever since this there have been many other problems that have likewise been proven to be uncomputable, most often by finding a way for "If we CAN compute X, then by doing Y and Z we can then use X to solve the Halting Problem." But as we know that's impossible, then X must ALSO be uncomputable.
I wonder is that has resulted in people ruling out things that almost solve the halting problem.
It wasn't a discovery; philosophers had already contemplated the "this statement is false" concept long ago; Turing merely framed it in computer terms.
@TheAkashicTraveller it is definitionally impossible to solve the halting problem. You can't almost solve something. It's a binary thing: either it's solved or not. An unsolvable problem isn't unsolvable because it's difficult to solve, it's unsolvable because it is a logical impossibility. The problem inherently contradicts itself.
@- Keep in mind though, there are a lot of ways to resolve this "this statement is false" "paradox", but you can't do that for the halting problem
It reminds me of np problems and how you can convert from one to any others, so that if you show one np is p, then all are.
I'd forgotten about this, nicely explained without overcomplicating, thanks.
I am doing my masters in cs and I think this explanation is great. Now I fear that I do not know enough about Turing machines :o
If you use the output of the "opposite" machine as input, you'd then have to give that machine it's own input or the input is incomplete. Given a set of input doesn't start with incomplete input, you can tell whether or not it will halt. What am I missing?
I wonder if, although it's impossible to create such a program, it's possible to create a slightly less powerful version that only checks for simple errors (such as a while loop that has some state that when reached will never end)
Of course. Its possible to check everything a human could check and more. Given unlimited compute, checking all proofs that would fit in the universe to see if they are a proof the code does or doesn't halt is trivial.
I'd hope that computer scientists would know that you're giving a simple explanation to people that you'd likely confuse or lose going really into depth on coding and internal workings of a computer, This form makes it so much more accessible to people like myself who have an interest or curiosity.
One of my college math professors with "Scott" in his name introduced this problem to me, and another professor with "Sean" in his name taught me about Turing machines. Now I'm seeing a script written by someone "Sean" and some "Scott" talking about those topics on ID-tv. What a moment.
You are the lucky pigeonhole in the pigeonhole problems
This compliments the concept of the "opposite" machine bizarrely well
I watched this video a few times before and was always amazed at the "you just booted straight into a programming enviroment". Why don't we have that anymore? Today I looked at the linux terminal I've been using daily for all these years and realised bash/sh is exactly that
This is the kind of concept that actually, really, push the humanity forward. It's ground-destroying. Just imagine the heights of what Turing proved (not to mention so elegantly)
*groundbreaking
You should have shown the shortest example of a program that we currently can't determine if it stops or not. The shortest one I can think of is this one: "Pick a positive integer>1. If the number is even, then divide it by 2, otherwise multiply it by three and add one. If the new value is 1, then stop, otherwise go back to the beginning and start over with the new value." I suspect that you can program this in APL in a few short characters, perhaps ten characters. That program should be your video's thumbnail.
I would love to see a more in depth version of this video.
Veritasium's video "Math has a fatal flaw" covers some of this with a focus on the limits of math culminating into computing issues.
Yes. But you can write programs that can determine on a class of programs that "makes sense" for you whether they will halt or not. If such a program says "yes" or "no" then the original program is (not) going to halt. If, however the program runs for a long time without giving an answer there is a decent chance that the program is not going to halt. In practice, code checking can be automatized to some extent if the programmer uses certain coding schemes.
Finally watched a Tom Scott video that isn’t from 3 years ago!
This comment's gonna be really funny in 3 years.
Yum.
I know that feeling
Ive started from 10yrs ago video, watched a bunch of 3yrs ago video and i m here now and this comment makes sense
I can totally relate to this
Nice video, but the logic was a bit broken during oversimplification, as in the video "halts" was able to determine the result only by program, without input. In original version "halts" was working with program-input pairs. "Opposite" was taking no input, feeding itself to "halts" and doing the opposite, so it should get the same result every time.
Thank you, I was really confused by this video.
But then what was being fed to the internal "halts" inside the "opposite"?
@Vandelay Industries "Opposite" with no input, as opposite doesn't require any.
I love the energy you gave to the disclaimer for the computer scientists
Nice one! But the solution to this problem is actually very simple. The halt or stop will go for forever if it is fed into itself. So all you need to do is feed this double problem again into itself. It will stop for otherwise it will go on for forever. Or am I missing something?
Anyone who wants to learn more about this should read “The Pattern on the Stone” by a bloke called Hillis. It’s very interesting and goes to appreciable level of detail.
So it may be possible to make a machine that can determine halt/no halt in 99% of cases, but not all cases.
+1 for vanishing in a puff of logic...
Alan Turing was also a vanishing puff
careful where you stick the fish
Yes, I'm tempted to make a rude comment about Alan Turing. Just I don't want to.
Babel fish go brrrrrr
@lightlysalted Don't panic
As a failed computer scientist I'll say this is well explained for any non computer science student
i'm not a computer scientist whatsoever but what had always bothered me about the halting problem was that it seems to only cause issues when dealing with a very specific type of self-referential "paradox" problems. is there a definitive answer to whether this is the only problem or at least one of a finite set that causes this? or in other words, would it be enough to add some sort of "except for self-referential logical paradoxes"-disclaimer to hilberts initial question and we'd have a beautifully working semi-turing machine?
A remarkable thing is that real computers always have to work with a limited amount of memory, so in theory you could step through a program and keep track of all of the states it has been in until it halts or reaches a previous state, at which point you can be sure that it will loop forever. However, the upper limit of possible states grows exponentially with the number of memory cells you have, so this bruteforce approach is not feasible in practice.
Reality is a bummer. As an engineer, if I find a problem I cannot solve algebraically, I just find a numerical solution that's within an arbitrarily small margin of error. Heck, you don't even need to know if it is solvable, just use numerical analysis every time a problem looks too hard to solve. Reality is fuzzy, "good enough" and "perfect" are the same, within your margin of error. ;)
This video leaves me with this thought: Why is it impossible to look that the instructions a computer executes and tell if they will loop? A computer itself "knows" when it loops (because it wouldn't create a loop if it wouldn't be given the instructions to do so), so why can't this machine exist? I think that the "halts" machine would actually get stuck itself when feed this loop, because it has to do infinite processing to determine the outcome.
I have worked on Computers my whole life and I never knew this, thank you.
It's interesting to see that the English word "computer" comes from 'compute' + -'er' (person or thing doing an action). - In Swedish, we have the word "dator", which is a portmanteau of 'data' and 'motor'; an engine that runs through data. Quite clever.
In German it's Rechner and basically means calculator, or... well, computer. Although the Anglicism "Computer" is more common nowadays.
In Chinese it literally translates to "electrical brain"
@Unicorns’ Pilot That makes sense. Although the irony is human and animal brains are electrical too. Not sure about tiny things like bacteria though.
That construct exists in most language. The concept is called (in English, of course) the 'active agent' form of a verb. The do-er.
Mike Spearwood I guess “semiconductor brain” doesn’t have as much of a ring to it?
I’ve never seen someone who looks so old yet so young at the same time
agreeedd!!
Hahaha
Like a very wise teenager
Maybe he's a paradox! 😳
It seems you do not know the German politician Philipp Amthor :D
When I was studying Turing I tried to understand this but oh my god I didn't find any source in the entire internet that explained it well and I never understood it Thank you so much
I understood what he's saying, but the concept still doesn't make sense, the program before it is entered into itself isn't complete, it's missing a data point. A program is a process, it doesn't have a result until you give it a reference point to start processing. I think the nuance might make it more convincing though
@Prophetic ShadeZ Well that's because it's oversimplified.
This has been the clearest statement of the P NP and the halting problem I’ve seen. Thank you.
You mean R and RE
I wish they brought that feature back (basic programming environment). It would be trivial to add a programming language with an IDE to every PC. I guess there maybe issues if security and liability and support if they are abused.
Ok, but what I really wanted was an example or walkthrough of a different uncomputable problem. Everyone knows about the halting problem, but anyone's intuition must tell them there's gotta be infinities of different classes of uncomputable problems that are probably all "the same", like NP-hard problems
Just a clarification: it’s not just that there’s no computer that can solve these problems, it’s that no algorithm exists that can solve these problems which means that there’s nothing at all that can solve them (as in no human can solve them either).
Exactly.
if I remember correctly even if there was an oracle machine that couldn't be encoded as a turning machine and solved the halting problem it creates a new class of problems we can't solve
As far as I know (learned this couple of years ago, my knowledge about it might be dated or proven wrong) a sub atomic particle passes from both sides "obstructions" simultaneously. This program might be possible with quantum computers. It loops infinitely and does not loop at all simultaneously.
Quantum computers don't increase the number of solvable problems. That is, any problem that is not solvable by a traditional computer isn't solvable by a quantum computer. Quantum computers just solve certain kind of problems more efficiently. A Quantum Turing Machine can be simulated with a traditional Turing Machine, so any problem solvable by a quantum Turing machine is solvable (just slower) by a Turing machine
As someone who has TAed an intro Theory of Computation course several times, this was a really good layman's explanation. Of course one funny thing I like to point out is that for any computer that we can ever possibly hope to build, the halting problem is actually solvable. This is just because unlike a Turing Machine, computers we can actually build don't have infinite memory. They're not Turing Machines, they're finite automata. This means I can look at the "state" of a particular computer executing any program (the contents of its registers, memory, disk, etc) and wait until either the the program halts, or I see the same state appear twice (in which case I know the program will loop) In practice however, this is obviously infeasible. Just considering 8GB RAM for the moment, that's 2^(36) bits so 2^(2^(36)) possible states. Also, interestingly, some low-level languages like C aren't in fact Turing-complete because the C standard defines a finite constant for the width of a pointer in bytes and the number of bits in a byte, which implies that the amount of addressable memory, and hence the number of possible states the program can be in, is finite. This doesn't actually rely on the hardware limitations i mentioned before. Or rather it demonstrates that those limitations are built into the C abstract machine. Another funny consequence of this is that all C programs that halt run in O(1) time. Since they halt, their runtime is bounded by O(2^(2^(CHAR_BIT * sizeof (void*)))) which is a constant (albeit typically a very, very, large one)
interesting take on the subject
I mean, if talking real world, it would eventually halt given the heat death of the universe (or a power cut) but this doesn't solve the logic question
Theoretically, couldn't you put in a special paradox case? If it's a paradox and it detects it (Hypothetically), it could put out a third answer of "Null". So it either answers "Yes", "No", or "Null". If we take that into account, would that count as the computer solving it if it detects a paradox?
The paradox isn't really paradoxing for me. What a program does depends also from the input. So it is reasonable to me that a program with no input will halt, but if you give it a specific input (eg his own code) will loop. Or vice versa. The 2 programs "opposite" are different because their input is different
Tom: "The, uh. The... Uh. The. Decision Problem" Me: (laughs in german)
same
Same lul
Laughs in Dutch
*laughs in bilingual*
germans laugh?
why did this video explain the halting problem 1000 times better than my lecturer ever could
This feels like Russell's "Set of all sets that don't contain themselves", but on a computer.
Yes, exactly. Russell's or Cantor's "diagonal argument" was very likely the inspiration for this proof.
At last a teacher on the internet that explains it ......and knows his / her subject
What a philosophical video, it was really nice !🤩👍👍
If you feed that program into itself, doesn't that just mean you haven't given it the "full" program? Because the program needs an input in order to function. Maybe if you give it the program WITH the input, it could determine something?
This is what we might call "The Strong Halting Problem": Question: Can one algorithm determine whether another will halt? Answer: No, because if it could, it still couldn't when applied to itself with a "negation" module appended. So, how about a "Weak Halting Problem"? Question: Can an algoithm determine the halting of another, provided the analyzed algorithm does not contain the analyzing algorithm? Recall Russell's paradox of the "set of all non-self-containing sets", and his proposed solution of a hierarchy of self-containment.
Still, the concept of "not containing the analyzing algorithm" isn't really well defined. Even if it doesn't literally contain it, it could contain something isomorphic to it. The big example here is how Russell and Whitehead made a system that talked about numbers but not about itself, and then Gödel showed that it could manipulate those numbers in a way that made it talk about itself, leading to the usual self referencing paradoxes.
The whole point of Turing's contradiction proof was NOT a counterexample that showed that "ok since I found one case where it doesnt work then it can never work for ALL cases" The proof was more like "assume it's possible, that assumption leads to literal nonsense, hence the whole notion of a "halting machine" is literal nonsense and is not even a coherent idea (even if the incoherence of the idea is non trivial to see)" I dont see how relaxing the conditions of such a machine would fix this, I feel like the proof strongly suggests (even if it does not prove, I'm not wise in the ways of decidability enough to know haha) that the machine is simply impossible as a logical concept Again that's complete non-rigorous bs that comes more from gut feeling rather than proof
This wouldn't work. You would need to specify what does it mean for an algorith to contain another. If I make a little tweak that changes the literal program but all the outputs remin the same, is it the same algorithm? This will probably lead to a definition of equivalent algorithms: Two algorithms are equivalent if and only if they output the same thing when they receive the same input. Okay, that one is solved. But now you need to verify that there is a program that can check if two algorithms are equivalent. This program can't exist, as it would have to go iver every posible input and wouldn't halt. Maybe you can think in other ways of solvibg the "contains the analyzing algorithm" but the problem will remain, verifying wether two algorithms behave the same is not computable.
There is a different way of proving the halting problem that doesn't rely on passing the machine as an input to itself. You can define a function that no turing machine can do (essentially, number all turing machines and all inputs, and then when given an input, output the opposite of what the turing machine with the same number would output on that word), and then you can demonstrate that, given a turing machine which solves the halting problem, you can make a turing machine which accepts the function that we just found to be impossible.
@Jarred Allen Is the set of all turing machines countable?
Hilbert figured out the best way to find an answer for a question is to answer incorrectly and let someone else correct you.
I just had an algorithms final. This made way more sense then how we learned in class.
In 1987 I had this taught to me at Arizona State University by a professor whose English was so indecipherable that 50% of the class failed. Turing machines and pushdown automata are already hard enough if you can understand the speaker. I studied so hard to get a 65 on the halting problem exam. Brutal. Today I understand regular expressions as if the skill were born into me. Do something enough, and we get to understand it very well.
David Hilbert: "I look very smart and trustworthy. Therefore I will wear this hat to dispel that image."
Was looking for this comment.
I think the hat makes him stand out amongst other mathematicians
I mean, it makes him quite a bit taller. Probably easy to find in a room.
True. The above statement is false.
We need some symbolic notation to be sure
Reminds me of Godels incompleteness theorem. I wonder if you can restrict the halting problem to a subset of all possible programs, ones considered useful or realistic, and answer the halting problem on that subset, similarly to how measure theorists restricted measurement to sets that were nice enough, which they dubbed measurable.
The editing is top notch in every video.
Weirdly enough, though this was only tangentially related, it helped me better understand how Magic the Gathering can be used as a Turing Machine.
Do enlighten me
Because Science already has a video doing exactly that
Same with microsoft power point, same with HTML5+CSS3. The important thing to know is that a Turing machine can compute *anything* given enough time. Turing machines (aka computers) are actually quite powerful
Chris Wyllie Did you watch the video?
@Chris Wyllie Correction: A turing machine can compute anything that is computable
Alan Turing was a freaking legend
There's also gotta be a program which will go on forever with out looping, similar to π or √2, but in some sort of code form.
There a contradiction going on there, in that paradox: A decision machine goes yes or no. Neither of those are loops. So the answer to whether it will loop is always no. -Or, if it may have to loop to determine the result, then it's not about the program, but the input.
Honestly, your simplifications are fine. The only thing I took a little issue with was reaching the end of the instructions. That's simplifying to the point of being incorrect, but hey, I can see how that might make it easier to understand, so it's all good. I probably wouldn't even have said anything if it weren't for the constant "sorry for oversimplifying" :P
I love how he replaced that German word with an English one, but just after some hilarious waiting time 😂
So basically, such a machine is impossible because its existence will contradict itself
yes, that's the video
But since it can not exist it also can not contradict itself! Therefore it can exist....
@Kamil C. yep, that's the paradox
Only if you feed it an infinite recursive stack as input.
@Vecheslav Novikov I suppose you're right. The machine gets another machine as input. But that input is the same machine getting the same input itself. That's an infinite self-referential loop of machines which basically tries to compute the answer to the question "Is the answer 'No'?". That's a paradox question with no correct answer so of course computers cannot find an answer. But apparently it's a big achievement to proof mathematically that you cannot tell the answer if there is none.
The thing is that the moment we understand how the brain works, computers can advance into a whole new world. From picture analysis to psychology treatment. Simply everything
lolwut?
6:07 can someone explain this better to me? If it thinks it will halt, it will loop. But that just means it will loop given this specific input. Of course, if we take all of this again and take it as another input, fair enough it will halt, but I don't see where the self-contradiction comes from, since we never stated that we refeed its output infinitely
Clearly this went right over your head...
@Cereal Killa What an explanation!!!
@Yash Sharma I have my moments.
One way to think about this is to observe that in order to have a machine that can answer a query, the query must be finite: for example, a program that finds the largest number does not exist, because it would need to be "x = 1 + (1 + (1 + ...))". If a question is impossible, so is the answer. To get OPPOSITE to halt, you ask it "do the opposite of (a program that prints something rude forever)", and to get it to loop forever, you ask it "do the opposite of (a program that prints hello and exits)". But when you feed in its own source code, you are asking it: "do the opposite of (a program that does the opposite of (a program that does the opposite of (...)))", and this query expands infinitely. A machine that answers an infinite query cannot exist, therefore OPPOSITE cannot exist.
The halting problem is solved in Ethereum by charging for gas. You might have an infinite looping program. The solution is to charge the caller to pay for it! (And that's also why there is a gas limit, so you set some upper bound to what is acceptable if it starts looping.)
This might be a naive question but it seems like the code fed into the halts/opposite program needs to be code that can be executed. The "halts" program was originally defined as a program that takes as input code, so when you say that you feed "opposite" to itself isn't that ill defined because the code you're feeding it doesn't "run" without an input to begin with?
I feel like they can't solve everything but if you are to look at solving if a problem can halt, you look at it from the point of view of the computer analysing the code rather than trying to run it and see what happens. Maybe with something like AI taught to program it could identify a situation like a loop/while loop that would be true and then return it as false if not. Additionally I guess you could also think of an infinite loop in terms of a person's lifetime, as in it looping for the entire lifetime could be considered infinite allowing it to be solved but as you said, it is simplified to some extent whichever way you look at it xd
It's like the "everything I say is false" paradox but for computers
"Ummm... 'true'. I'll go 'true'. Eh, that was easy. I'll be honest, I might've heard that one before, though."
@I'm Very Angry It's Not Butter "For God's sake, you're boxes! With legs!"
I don't think this is a paradox since this statement could be false without contradicting the negation of "everything you say is false" which is "it exists something you say that's true". If the statement is false, maybe another statement you said could be true, who knows. A real paradox should be more specific to the statement like "This sentence is wrong."
For what it's worth, the answer to that paradox is that they're lying to you. Not /everything/ they say is false, just one statement. It should also be noted that most paradoxes are less logical contradictions and more "failures of sentences to form a concept" or failing to take into account a 'third option'. To use an example of the latter: What happens when an unstoppable force meets an immovable object? They pass through eachother. The force does not stop, the object does not move. To use an example of the former: "Can God draw a square circle?" No, because the term 'square circle' doesn't actually mean anything. Similarly, God could not create a tornado over water, because then it'd be a water spout.
I got my Comp Sci degree 30 years ago and really enjoyed this, thanks
sounds very similar to Godel's Incompleteness Theorem, you should make a video on this as well!
Not technically a mathematical solution but I mean the computer could just simulate the execution of the code and in a separate thread keep track of the length of each frame and if it exceeds a certain limit chosen by the user than it will tell you that it has encountered an infinite loop. Your answer is indeed still correct, but not necessarily in a practical sense. Sometimes brute force is just the best method.