The Halting Problem - An Impossible Problem to Solve
Vložit
- čas přidán 19. 07. 2018
- Start learning today with SkillShare: skl.sh/upandatom2
Alan Turing proved that the Halting Problem was impossible for Turing machines (computers) to solve. Come find out how.
The quantum computer game I talked about: phys.cam/game/
This video was co-written by my super smart hubby Simon Mackenzie.
Hi! I'm Jade. Subscribe to Up and Atom for new physics, math and computer science videos every two weeks!
SUBSCRIBE TO UP AND ATOM / upandatom
Visit the Up and Atom Store
store.nebula.app/collections/...
*Follow me: @upndatom
TWITTER: upndatom?lang=en
INSTAGRAM: / upndatom
Check out this PlayList for a taste of the channel:
• Popular Uploads
A big thank you to my AMAZING PATRONS!
Paul Kendra, Harsh Tank, Alan McNea, Daniel Tan-Holmes, Simon Mackenzie, Yoseph, Andrew Pann, Dave, Anne Tan, Ayan Doss, Marc Watkins, Sung-Ho Lee, Todd Loreman, David, Susan Jones, M.H. Beals, Doug Cowles, Stephen Veitch, Renato Pereira, Simon Dargaville, Dean Madden, Noah McCann, Robert Frieske, Magesh.
If you'd like to consider supporting Up and Atom, head over to my Patreon page :)
/ upandatom
For a one time donation, head over to my PayPal :)
www.paypal.me/upandatomshows
Other videos you might like:
What is the Schrödinger Equation, Exactly? • What is The Schrödinge...
What is a Singularity, Exactly? • What is a Singularity,...
Y CN U R34D DIS? • Intro to Information T...
Sources
www.cs.virginia.edu/~robins/T...
index-of.co.uk/Theory-of-Compu...
www.huffingtonpost.com/entry/...
Music
www.epidemicsound.com/ - Věda a technologie
WHOOPS 1 isn't a prime. The computer would have stopped at (2+2), my bad! Thanks for pointing that out everyone :) I can be a bit ignorabimus sometimes.
Ignorabimus maximus should be a harry potter spell. :)
We luv u nevertheless.
haha where the subject becomes stupid for a while?
Hehehe ahh yea, I'm imagining someone casting that spell on Crabbe and Goyle. Since they are already idiots... they'd be hilariously stupid. Actually half the plot of chamber of secrets could have been bypassed cause when Ron suggests tricking them into telling them what Malfoy knows, Hermione's response is something like, "not even they are that stupid". But if she had such a spell they wouldn't have had to spend half the semester brewing polyjuice.
Up and Atom woah u have only one dislike on this vid
Platypus wins, those venomous spines are no joke
i love you
haha there needs to be a video on aussie animals. Maybe even all the spiders and snakes o.O
there is its called "is Australia op?" czcams.com/video/TrsaXzmqShM/video.html
also there is a "spider tier list": czcams.com/video/lOfUZvOZ400/video.html
and "Optimizing the Snake Build": czcams.com/video/bWOe2Znb74I/video.html
No, the Wombat will just sit on the Platypus and squash it... 👍😊
Wait TierZoo, you’re into comp sci and math?
These guys didnt even had computers when this was proposed, I love it. Alan Turing was a visionary.
Does that name have to do with a turing machine
Mark Daniel a Turing machine is a model for how a storage device, a table of instructions encoded into the storage device and a machine that follows the instructions to modify the data on that storage device based on those instructions. It’s a model that was proven to be able to solve any problem that’s solvable by a computer given enough time and storage. And it’s ideas like this that made computers possible in the first place
they might not of have a modern computer, but before electrical computers there was mechanical computing machines.
then punch card computers with no screens.
An electrical system is a basic computer and the transistor is loosely based on the on/off switch on=1 off=0
vaccuum tube was the first automatic switching device at 1903 a solid thirty years before Turing made his machine then the transistor debuted in 1947
Turing made the first automatic sorting algorithm in a machine in 1936
@@markhaus no. the vacuum tube was the first step into modern computing. Turning made a sort function algorithm and had a mechanical machine sort using if thens cards until the sequence completed.
3:53 - I'm sorry, Dave, I'm afraid I can't do that.
Seems a few people are either trolling or missing a fundamental detail of the particular proof. Hal is assumed to be a *general purpose* program that can be run on *any* input program and it always provides the correct answer. Because Hal is defined to work on all programs, it must be able to work on itself since Hal is, itself, a program. The thing I think a lot of people are missing is that this is a proof that the halting problem cannot be solved in the *general* case. To prove that the general case cannot be solved, you just need to find *one* counterexample.
This says nothing about specific cases. There are plenty of specific cases where it is possible to identify if a program will halt. The existence of those cases does not invalidate the proof. The proof is simply telling us that there is no magic box that will work on every possible program. Basically, it means there isn't a magic shortcut for solving Goldbach and other problems.
thanks for your comment because the video doesn't explain this at all!
Still, I don't know what this all has to do with a program that has to test all numbers to infinity (like the goldbach problem). Of coure, it runs forever.
@@Falkdr The "Goldbach solver" program will stop if it finds an even number that cannot be represented as 2 primes. So if you could run "Hal" with the goldback program as input and it returns that the program never halts, the goldbach conjecture is proven true. If "Hal" returns that the goldbach program does halt, that can only happen because the goldbach program found a contradiction - an even number that cannot be represented by two primes - and stopped, and you have proven the goldbach conjecture false.
@@uchian No, Hal would never return anything because it has to go through all the numbers that are, to test them (so infinite). You'll have to wait forever for the answer.
It sounds Up&Atom was just asking "does Magic exist?". As far as we know, it doesn't, so there doesn't seem to be all to much behind this video.
@@Falkdr In the halting problem, 'Hal' does not run the program to determine whether it halts or not. It would determine it through some (unspecified) analysis of the instructions in the program that returns a yes or know answer as to whether the program halts or not. The proof discussed in the video means that the the "unspecified" bit of the above statement is mathematically impossible in the general case.
I got that, by unspecified you mean 'magic'. Its not that bold to set up an impossible claim and proof that it is impossible, imho.
I don't think the 'halting problem' would've been huge riddle in modern days, back then it might have been a great analysis, though.
5:07 "Barrie can't both run forever and halt" Schrödinger's cat is calling fake news on this one.
f. g Did you just actively interact with Schrodinger's experiment?
Ibraheem Al hadede Yeah, how do you think I am here? 😂
But Hal is "observing" barry
But what do you do with a dead program/cat?
@@Trident_Euclid interact*
Studied this back in the 70s in Cambridge when the people who had known Turing were still lecturing. This video brought back some wonderful memories. Thanks.
BTW the entire university computing service ran on an IBM 370/165 with 3 megabytes of RAM back then.
Hilbert's Nemeses: Turing and Gödel :D
Hilbert KNEW about Gödel's Theorems, but rejected their conclusions, proving that even the most logical mind (Hilbert's) has an logical conclusion that it cannot accept. Even the King of Mathematical Reasoning had his weak points.
I remember in the good old days studying computer science and first hearing about "The halting problem" it seemed odd and trivial to me at first... that is because I didn't understand it, I mean... I didn't understand why it was such a big deal. The proof done by contradiction was brilliant ploy by Turing, I'll never forget how astonished that I actually got understood it on the first run-through (that rarely happens!)... but you made me feel sad for the way poor Hilbert was broken hearted in your animation... but, as you rightly pointed out, he does have his own space named after him, so there is that...
I solved the halting problem by unplugging my computer and crying.
Melthornals computer halts. Must run forever.
“Will I ever stop being a disappointment to my family?”
A’ight Jade, I’m gonna need you to stop recording me while I’m “working”, we’ve talked about this.
that shade tho
I just found your channel, your videos are great! Keep up the good educational videos! :)
Hey Keystone! Nice to see you here :D
MrWilliam932 hey! ;)
You have one of the best animations for science videos, period.
Ehm... 3blue1brown, need I say more?
Physicist in training here from NYC (third year). You've got such great content! Very concise, descriptive, and VERY entertaining. Keep it up :D !
It’s amazing how smart and ahead of his time Turing was. I wonder what was his thought process to even fathom such concepts and ideas in an era where computing was still primitive in comparison.
Really like the variation of such intriguing topics you make videos on! Keep it up, super fresh!
This is so good Jade, probably the best explanation on this question I've ever seen!!
What if we put the Barrie program on a quantum computer where it is potentially both running and halting simultaneously, in a state of superposition. I think I have solved it. ;-) Great videos, keep them coming.
But even then it has to resolve to one state. ;)
Barrie and Hal are just entangled particles. Also, Einstein hates them!
@@zeeshanbhat What if it is a super-conducting barry?
Funny that you should say that actually, but it turns out that not even quantum computers can solve the halting problem and that the proof for it has some major implications throughout physics and maths:
www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/
@@shadiester I carefully and slowly read the article you posted and if I'm honest my understanding of it far from complete. If my view is correct, without entanglement the proof would remain unsolved. Cheers
You win. You win all the things. I took computing science in university, and when we were discussing this very topic, I couldn't wrap my mind around it. I believed the conjecture that a halt detection program could not exist, but I felt deeply unsatisfied with the proof. The "Barry" program felt like a cheat that inherently proved absolutely nothing. Seeing your video made it clear what my professor had missed in her explanation: The halt detection program took "Barry" as an input and fed that output to "Barry".
This is absolutely the best explanation I've seen for this paradox! Thank you so much!
Turing's use of self referential contradiction in the halting problem in (1936) reminds me of Gödel's incompleteness theorem (1931).
Scott Busby Yeah he was heavily inspired by Godel's approach to the completeness question
Turing was inspired by Gödel. I was disappointed she mentioned Hilbert, but didn't give Gödel credit. Still, I can see making the decision to keep the video under ten minutes.
Scott Busby: And that's no coincidence. Turing's Halting Problem, Gödels incompleteness theorems and Church's Lambda Calculus are functionally equivalent. You can convert one model into all of the others.
Turings halting problem was a rephrasing of gödels incompleteness theorem.. gödel was the first one to see it and the real genius.. Turing was a big fan of gödel btw.. this video is misleading!
I really love your way of explaining complex knowledge/theorms in very simple words along with cool animations. 😍😍
I always hated thoery of computation, but now I don't 😊
Super good videos that you have made. Very clear and also entertaining. Good job.
Wow that was so awesome. Your channel will become huge ,i just in love with your channel's content.
Great video, wonder if in a quantum world it could run and halt at the same time :)
"Am I still a disappointment to my family" - that hit home...
Great video! Your channel is amazing!
In fact, a Turing machine has been created with, I believe, 29 states that halts if and only if the Goldbach conjecture is false. The step function S is the maximum number of steps a Turing machine can run before it must either halt or run forever. So, if you ran the machine for S(29) steps and it didn't halt, you'd know the conjecture was true! Of course, the halting problem proves that S cannot be computed by a Turing machine, so we can't actually know what S(29) is. However, we do know that S(17) is greater than *Graham's number*, so the age of the universe isn't even pocket change compared to it.
Greetings from a brazilian fan, i love your channel!
Looking forward to videos about the mathematics behind machine learning (backpropagation derivatives, error function parameters, random minibatches, what is matrix calculus and why GPU's parallel process is a great solution for this, etc)
can't wait to see them =)
sorry my bad english
Achei q n tinha br aqui
Brilliant! A simple way to describe a seemingly complex problem. Thank you.
love the way you explain everything with such ease and smile.
"There are simply some problems we cannot solve." Yes, *within some formal system, like ZFC* that has arithmetic. It does not mean there are some problems that are simply fundamentally unsolvable, whatever that means.
Just like there isn't some genie/oracle magical program that can tell you whether or not *any* *program* you feed into it will not run. That does not mean you can't build one for specific cases.
It's a great problem. I remember I loved the proof when I first heard about it. I also really like another problem that can't be solved called Post Correspondence Problem and that's because while the halting problem at least sounds like something really hard to do, PCP is a problem that seems like something easy. Something we can do by hand when given an example input. And how the hell can there be no step by step method solving something like that for any input, given unlimited amount of time and resources? It still blows my mind that there isn't, but I've seen the proof. But way more complicated than this one. And PCP can be applied to proving a bunch of other things aren't decidable. Darn, the laws of our universe are harsh! It's not enough we don't know the answers to so many things and going to keep trying to answer for thousands of years to come, but we already know there are things we'll never answer! That's just depressing!
This is just more complicated version of "this sentence is false".
I LOVE this and love logic! This made me smile :)
Your explanation is really awesome as always !!! Keep going :,)
5:07 Now I want someone to try this on a quantum computer.
Strangely enough, a quantum computer would not help: Halting Problem remains impossible.
@@DavidFMayerPhD But consider, in a quantum system, superposition gives 'Hal' a third option to return, where it is both running and halted, simultaneously.
@@twistedbard That is NOT an answer. A result means a SINGLE result, not a superposition of results.
@@twistedbard also, what would "both running and halted" even *_mean_* tho? Does the input machine stop or not?
Hi there, I was thinking of starting my own channel and I like this kind of topic. But when I saw the video I think you could have an error on it. I should check on the original paper, but I think you are missing something important which is the input of the input.
For instance, in 4:19 you are talking about the program Randy, the program Randy could Stop or Run forever without having into account the input of Randy, which implies that Randy parameters are not important on if the program Randy will run forever or not. But you have programs that its input decides if they will run Foverer or not.
When you state the proof, your say in 4:45: You said that Halt receives Halt as an Input, in an explicit way is: The program HALT receives as Input a HALT program. But you are missing one parameter there, which is the Input of the Input, Halt can say if the Input will stop or not because The input program could receive inputs that makes HALT or NOT.
I know its confusing, but maybe I Skipping something. Thanks
I initially got confused about the same thing. Took me a while to realize what I have missed. The key is at 4:08.
HAL can answer the question: will a program X with input Y halt or not? So HAL has 2 inputs, the program (X) and the input to that program (Y).
BARRIE is different, it only takes one input, a program (X). It then asks the question: what would HAL answer given program X with input X, and then does the opposite. That is, the input to X is X itself.
@@AdrianTaga ok but if X is a program that needs an input Y to run, X is not a valid input for X itself, at a minimum it's not complete, there has to be a Y input, of the appropriate domain, at the end of the chain.
@titusfx not quite, at 4:45 it is BARRIE not Halt that receives itself as input. (And unlike Halt, Barrie only takes one input.) Also, Randy would later similarly received itself as input, that's why she wrote "Randy(Randy)". At 4:19 it is merely shown that the "X" that Barrie receives as input will in this case be Randy, then Barrie will work on it as in the description: "Do the opposite of what Hal predicts *about program X and input X."* :-B
@@AdrianTaga as @Daniele Messina says, Barrier will have the input X, which is Barrier, so the input X will need another input (and that will be forever if you just put Barrier as argument). I have got this doubt for years, since University. And I have the same problem understanding the paper and this exact point. I could be skipping something...
@@irrelevant_noob What you said is correct. But that's not what I'm trying to say (I wrote about Halt, trying to "expand" Barrier). What you said about randy is correct. So, instead of thinking on Randy, try to change Randy with Barrier, which is what Turing did.
Barrier will have the input X, which is Barrier, so the input X will need another input (why? Because is Barrie, so it needs another input, which that input can not be, Barrier, because it will need another one, and so on, until the infinity)
Awesome video, very well explained for a math novice like myself.
Wow, great explanation! Best one so far!
3:03 1 is not a prime.
soz my bad
2+2, happy now?
i just want to wrote this
How would you write 3 though
Neither is a composite number poor number 1, 1 is the loneliest number.
I've had programming ide's pop up a warning saying a subroutine would run forever.
its more along the lines of it not having something that would end the loop rather than it never finding an answer.
you would need a program that predicts the future in order to know if it would halt.
That could be as simple as making sure you don't have something the compiler compiles to the equivalent of while(true) {code}
Very interesting explanation. Thank you.
thank you so much that was so awesome.
Besides the cool topics and easy-to-follow explanations, I think what sets this channel apart from many similar channels is the animations :)
Incredibly intriguing and took me a couple watches to actually understand it 😂.
I'm glad you were able to get it! It took me a whlie let me tell you haha
You broke my brain in the best way possible. Thank you ☺️ I really enjoyed watching the video.
Love the drawings and animations!!
Computer, which is better: Pirates or Ninjas? Star Wars or Star Trek? ... .... 42.
A platypus would obviously win in a fight! That's not even a question.
haha i dunno wombats are pretty strong and have sharp claws
Because of you, I finally somehow understood the halting problem. The recursive representations feed onto itself of your video did it - brilliant I believe. Maybe a way out of the halting problem is the impossibility of feeding back a decider into itself, an ultimate decider that cannot be fed back into the programs - beyond the Turing machines. At that level, though it can take in programs and make a decision, it cannot be called program or computer, a totally different category. What is that thing, which is not a program itself, that could take in programs and evaluate them? Or we have a third option, we endow Barrie a recognition that it itself is inputted into the same evaluation, so Barrie could halt, loop or return 'not like this, not like this, we will run into a paradox.'
Great guy, turing.
Thanks for the video appreciate it! Keep making more
This channel deserves like 10X the subscriber count.
aww shucks ☺️
The classic "Trust me! I'm a liar."
If you are always going to lie, people can trust you because they can know the truth. Otherwise it goes to probability theory.
this is such a great video! please make more on computer science topics please
Love this video .... And bringing Alan Turing works other than the Bomb is pretty cool :) Thanks for that. 👏
Interesting fact: Perfect antivirus program is also imposible as proven by Fred Cohen, based on the halting problem.
that is an interesting fact :)
The halting problem doesn't just mean there are problems "we" can't solve. It means there are problems that are impossible to solve - by anything - ever. It means omniscience is impossible.
your conclusion isn't necessarily true. while it's true that there are problems that we cannot in principle find a solution for, that doesn't mean the solution cannot be known.so for example, i (imagine i am a magical being outside of time) could know all the digits of PI, but you, in your finite universe, because you don't have infinite energy and time, cannot determine them. you have to stop at some point.
then there are problems that have no solution in principle. those don't disprove omniscience. this would be like saying "god cannot create a triangle with 4 sides" and say "ha! no omnipotence!"
No. That's my point. It proves that nothing - not even a magical superbeing outside of time and space - could know everything.
By the way, a magical being outside of time is, by definition, impossible. For something to exist, it has to be in time and space.
Hmmmm... "For something to exist, it has to be in time and space." What about 1+1=2? That and all the rest of math, can math not exist without space time?
Math is a concept. Concepts aren't real in any material sense - they require an intelligent being to conceive of them. If you're arguing that god is merely a concept, I agree. But that doesn't mean he actually exists as a real being. Fairies are concepts too - they also don't exist as "real beings". I think it's about time we grew up and accepted that magical beings don't actually exist.
What about the multi-verse, our space-time doesn't connect to the whole thing otherwise they wouldn't talk about universes colliding and popping like bubbles. So IF that theory is true then not only is there something outside our space time, pretty much everything is out there.
I just discovered this channel, and I just fell in love... Also, very good video, this is like a computing-version of the Gödel Theorem
This was amazing!
Do you write your jokes by yourself??if so then you're a good comedian as well
haha well I'm glad someone thinks so...
@@upandatom 'G0LDbAcH wuz a L00zer' had me chuckling :)) Only proves that even the smarty-pants computer that can solve the halting problem would still struggle with grammar :p
Who makes your animations??
I do! 😊
impressive
I'm from Kentucky, and sometimes when I hear IT people talking shop, I'll put on a more southern accent than I actually have, and volunteer: "Y'all talking about computers? I only know two things about computers. How to turn it on, and that it's impossible in principle to design an algorithm capable of predicting whether the algorithm itself will ever halt, when presented with its own executable code."
Good simplification, love it
Your videos speak volumes for your level of intelligence. ^_^
Turing was brilliant!
No Turing was GENIUS :-)
GREAT EXPLAINING THANK YOU!!
This video is the best, I've searched a very long time but I did't understand anything, THANK YOU SO MUCH ❤
"who even has a space of his own" ROFLLLLLLLL!
0:32 "has his own space named after him" ;-)
Barry runs in a superposition. *Drops mic*
Why have I not seen your channel before!? I love it!
The Turing Problem reminds me of the thought experiment you did during your free will video.
Where a computer computes whether a person will be invited but can't tell them without changing the result.
1 is not a prime.
you're right. my bad.
You literally have an infinity like-to-dislike ratio right now.
Loved the Space Odyssey reference. Excellent video as always.
Hahaha! I love it, it's a beautiful application of Russell's paradox!
I don't get it. I'll try watching it again.
Question: Could a quantum computer solve the halting problem?
Azmeriah no. A quantum computer can do the exact same stuff as a normal computer. In fact, you can simulate a quantum computer with a normal computer. A quantum computer is just faster for certain algorithms. So both are formal turing machines.
@@macrozone I thought quantum computers can do less than normal ones
Diego Antonio Rosario Palomino I don‘t know. Tbh. Depends on if you can simulate s normal computer with a quantum computer. Could be that it can do less, because normal computers theoretically always give the right answer (or none) and you probably cant simulate that with a quantum computer. But we neeed an expert in complexity theorie for that
_You are the best. Thank you! Lmao when you talk about Hal and Berrie. Love it so much hahahahaha_
As always , AMAZING vid ! Keep up for the good work my love
Gödel... make a video about Gödel... pls
Would you kindly make a video about Gödel?
#BioshockStrategy
ok :)
Yay!
I think that the conclusion that the video apparently forces us to draw is that there are some problems that the human mind cannot solve.However Godel would have answered this apparent dilemma differently. Godel was a mathematical Neo-platonist and he asserted in one of his lectures that "Either mathematics is too big for the human mind or the human mind is more than a machine" and he agreed with the latter. What do you think? @Fabio Duarte
Well, I decided I can't just think through Goldbach's conjecture and say it is true... (I've been working on that one for over 14 years)... I'm halting my program you could say. Hahaha. However on a meta mathematics level I came to believe it is true. I don't think our minds are more than fantastically complicated machines, yet we aren't confined to the rigid rules of linear programming. But maybe we could be reduced to the equivalent of lots of simpler programs?
The meaning of life is 42
Bruno Henrik
Are you sure? 42 is the ultimate answer for the ultimate question. Not a mere question like 'what is meaning of life?'
And the ultimate question IS...
37 + 5
M of L: All living things from Man to virus seek only one thing, to increase the incidence of their genes. They behave in ways and display traits which, in the past, have tended to do so, according to a genetic strategy which, in the case of animals, is flexibly enforsed by a pain/pleasure program.
@@brunohenrik8025 What is (-80538738812075974)^3 + (80435758145817515)^3 + (12602123297335631)^3 ?
Since this "solution" test is just a repackaging of your previous "knight/gnave" paradox, it's use for such purposes must be questioned as valid. Every such application will obviously result in the paradox. It is folly to use a paradox to determine the validity of an argument.
OMG, you explained the stuff I couldn't even understand even after listening my lecturer, reading many slides and references. I cannot believe that the explanation can be this trivial 😂.
Thank you very much! Only if CZcams recommends it 7 months ago when I was still doing my Cryptography class 😂
I think the halting problem has a fundamental problem, which makes it much less general than it might appear. Now don't get me wrong, given its assumptions the logic is perfectly valid - but that's where the problem lies, in its assumptions. The only possible return values of our hypothetical decider-program are true and false. What happens if we add a third option: self-referential
The only time the halting problem occurs, is when the algorithm is fed with a modified version of itself. So what happens if a new version of the decider-program can detect versions of itself in the input, and when it does so it simply returns "self-referential? Now any type of manipulation of its outputs is utterly useless - Hal will simply always return "self-referential". The paradox is solved.
This doesn't mean that we've proven that a Hal program is possible, but the proof that he is _impossible_ now doesn't work. A program that can predict if _any program_ will halt, and always returns a boolean, except when the input program contains its own code (which is in only a very small amount of inputs), is completely possible by this logic.
To me the problem seems similar to saying computers can never solve division by zero. And it's true, if you define the division as a operation which takes a rational number (floating point for computers) and always returns _the rational number_ which is 1 divided by the input. This doesn't work, but the problem is that the definition itself contains the paradox: The output of one of the inputs, namely 0, is not defined, and thus does not lie in the defined output space of the rational numbers. Does this mean computers have to crash whenever they have to divide by zero? Of course not. The fix is simply defining the output space as "some rational number _or_ Not_a_Number". Paradox solved, a program which takes any rational number and returns 1 divided by this number _is_ possible.
That's boggling me, too. It's always so easy to think of cases that don't work to avoid doing them. Ok, you can't write that program with a yes/no output, granted. Doesn't seem to be a great leap to me.
Just write a program with 3 outputs, problem solved.
Does barry halt? "self-refrential", will goldbach series halt? yes/no.
This is a solution, technically. HOWEVER, such a thing would contradict what it was actually about, because of the thing where if the problem were to be solved for all cases, meaning we world not need this code. You are thinking actually of a workaround because of the issue that arises, and I like that. But, this is not programming for realities sake, rather what this is is magic computer science land, and also math land. Let's not think of what it means for the problem itself, but rather of analogous things to the halting problem. How about you try those?
There are some problems comuters can't solve?! That's so sad. Alexa make me happy somehow.
Superbly explained. Can you also make a video on first order set theory please. I heard we can write big big numbers like tree(3) and graham numbers with few symbols. Appreciate your support.
Such a profound problem with such a simple, elegant and even funny solution! I am amazed how often genius and beauty follow the same tracks
you don't even need a computer 42 is the answer to life the universe and everything
You are not a disappointment
I really enjoys your video. From Malaysia. It is really an eye opening.
Can you make a video where you connect the halting problem with Hofstadters concept of strange loops and also maybe the Fermi paradox. That would be super cool!
Dude, you're awesome! Where do you find the stuff to talk about?
awesome! Thanks
Superb, I fall short of words.
“Who do you think would win between a platypus and a wombat?”
That is the most Australian sentence I have heard all week.
But could you make a program that detects whether another program will halt that returns 3 possible options instead of 2? Where the possible outputs are "Yes it will halt", "No it will not halt", or "Whether it halts or not depends on my output".
Please do a video on Qubits and classical bits
Love your videos BTW
I like that idea :)
Wow this was an amazing explanation
Wooow hi, just wanted to congratulate you! This video is PERFECT! It helped me to understand the Halting Problem so much better. For real, thanks :). Wish you all the best and yeah, keep going with this amazing content!!