All about Hilbert's Decision Problem, Turing's solution, and a machine that vanishes in a puff of logic. MORE BASICS: ispulse.info/list-PL96C35uN7xGLLeET0dOWaKHkAlPsrkcha.html

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

Both my co-author Sean and I are worried that we're oversimplifying here -- but then, this series is called The Basics!

If you didn't want to simplify the Halting Problem into a video that was less than 8 minutes long, you shouldn't have made a video about the Halting Problem that was less than 8 minutes long. All joking aside, amazing video.

It's good that it was simplified that much, for young viewers like me it's great to help us understand all of your videos on more complex subjects!

Incredible video! You own what you do. And that is far better than worrying and never offering better.

what if you make the code run the code in quietion in the background and then if it loops it will for certain loop

The "Opposite" program needs an input in order to do something. Without an input, it sits there and does nothing at all. So if you feed the opposite program itself, the correct answer wouldn't be "halts" or "doesnt halt", it would be a third option called "Nothing happens"

Thanks for the flashbacks to CS classes. Ouch, my head does not comprehend advanced math enough to understand the full P =/= NP proofs.

On BBC basic you have too have a semi colon at the end of the print statement or it goes on to the next line

can u help at all ? im looking for Lander with sound fx? for the Acorn Archimedes A3000? thanks.

possibly meta-analysis could work here, while we cannot be 100% certain would could have a probabilistic answer, say we might know with 95% that this program will halt or not. Will a rock thrown from a building always hit the ground. What we know of the environment and it's initial conditions, can can supply a answer with a high degree of confidence. So we don't have to run the program to know what the outcome will be.

In what parameter would the answer be probabilistic? In computer science, there is a machine called a "probabilistic turing machine" (PTM) that is intended to model a certain useful notion of probability, namely roughly that a turing machine only has to correctly accept/deny an input more than 50% of the time. It turns out that PTMs are turing complete, i.e. they too cannot solve the halting problem.

Me: googles "Are there any problems a computer can't solve?" Computer: ERROR 404

Me : Pi

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 fi

So you're saying you feed the output of opposite back into itself? But dont you need some starting input to start it off?

Tom simplified a lot. In the real halting problem, we ask whether a turing machine halts on a specific input, and then a halting problem decider is a program H(program_code, input_to_program). The opposite machine only takes a single input; it is a program O(program_code). O calls H(program_code, program_code), i.e. it passes the program code it got for the parameter as *both* the program code and the input. Now, whether O(code_of_O) halts depends on whether H(code_of_O, code_of_O) halts, which by the definition of H again depends on whether O(code_of_O) halts. So O does indeed not need some starting input, because it passes the code it gets as both the program and the input to H. We can then derive a contradiction from this circularity because we defined that O halts if and only if H does not halt.

Love the Hitchhiker's Guide to the Galaxy reference there 👍🏻

As true as it is in theory. it's hard to think of real world problems computers cannot solve. I mean computers are basically extremely obedient and extremely dumb slaves, you can't ask a slave to solve the Riemann Hypothesis but you can ask him to file your taxes.

Is it like saying which way does the earth rotate? Do you think you know which way it rotates? Truth is it rotates in both directions at once. How can that be. Imagine your in space way above one of earths poles. You look down and see it spinning clockwise. Now float around the earth to above the other pole. And look down. You now see its spinning counter clockwise. Understand now? Everything is simply a relation to something else to define its truth. You can say is the earth large or small. And then look at the moon and say the earth is large. But now look at the sun and you see the earth is small. Its all relative.

The real question is are there any problems that a computer can solve?

Yes. Try to ask my computer why the internet is down.

I'm not too impressed, to be honest. This is just saying that logic machines can't solve a paradox - which is defined by being unsolvable by logic. I don't see the surprise there.

Advanced AI: Well, hello there!

So that's why paradoxes always make robots blow up in movies.

Me: googles "Are there any problems a computer can't solve?" Computer: ERROR 404

SOMETHING RUDE

Tom: Are there problems computer can't solve? Captcha: Am I a joke to you?

yes, naming a computer file a "CON"

Why is your body so small

<a href="#" class="seekto" data-time="372">6:12</a> thanks Douglas Adams. 👌

Life

I originally deleted this because I was afraid it was a stupid question but you know what I kind of just want to know...So I'm gonna leave it here anyway. I'm new to quantum computing, and I admit I don't really have a good understanding of it yet. But I was wondering, does this apply to quantum computers? The way I understand it, to know whether the program halts or continues, wouldn't you have to actually observe the result? So wouldn't it be that, in the case of a quantum computer, you COULD solve EVERY problem, but only some of the time?

42

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).

42

Yes. Computer can't solve emotional and feelings problems. Can't fix broken heart, can't do anything by its own actually

<a href="#" class="seekto" data-time="74">1:14</a> legit thats how gta online works

I feel that getting into a debate with Turing would have been a bad idea..

Yes, no Super Computer can work out why I don't have a girlfriend

Anyone remember GLaDOS?

I know! Those sometimes illogical mathematical textual tasks.

Why doesn’t Tom have a late night show yet..?

i mean, some computer found out that the meaning of life is 42

So... im German, so I could read that Dunno why I had to say that

Yes

Tom: Are there problems computer can't solve? Captcha: Am I a joke to you?

Tom: Are there problems computer can't solve? Captcha: Allow me to introduce myself...

Windows XP can't cure my AIDS

Only humanity, but maybe computers will fix that problem someday too. All hail our future robot overlords!

42

crash/destroy your computer? Please, let me know what the answer is.

42

@alida flus 42

When you live-stream (with face-cam) and you're watching your own on stream. You get a "droste effect" question: But what if you have that "droste effect", will it ever stop or

42

42

42

Just add a check that checks for an opposite paradox, and put a third output that tells the user that their mom doesn't actually love them because they fed a paradox to their machine, eh?

I know! Those sometimes illogical mathematical textual tasks.

Poke 808,234

"vanishes in a puff of logic" Aha now there's a subtle Hitchhiker's reference

our maths and computers cant..... what about aliens

What you could do is that you implement in the Code of the Programm some kind of Signature that this is a code checking programm and then the computer ignores te Part of the Code where the possible input would be the code itself. And I know that the Programm is than skipping some parts of a code and the answer would not be true, but the Code would check every other part of the code.

the hitchhiker's guide to the galaxy

Wouldn't the solution be to just make sure the prompt was never entered?

Best question to ask a computer is [any number]÷0

you filmed this at the computer history museum in cambridge, tom scott

I feel that getting into a debate with Turing would have been a bad idea..

I don't get it: Opposite has a case where it infinitely loops so feeding opposite into opposite should always halt

They really paid Turing back for his help.

Alan Turing: "Hey guys. I have broken through the german code!" British government: "Why are you gay?"

When you live-stream (with face-cam) and you're watching your own on stream. You get a "droste effect" question: But what if you have that "droste effect", will it ever stop or crash/destroy your computer? Please, let me know what the answer is.

"then it vanishes in a puff of logic" Hitchhiker's Guide reference?

It can’t solve my marriage

I'm not entirely convinced by the answer that inputting Opposite's own code into Opposite will create a paradox, but I assume that's a result of the simplification. What the Input Opposite's "Halts" outputs shouldn't matter at all to the external Opposite, it would only care about the output of the internal "+"'s reversing code. If you provide the Input Opposite with halting code, then + will create an infinite loop as the ultimate result of the code, and so the external Opposite would process that in its Halts and its + would halt the program. If you provide the Input Opposite with looping code, + will halt, and the external Opposite would then loop. If you're judging Opposite purely with its potential results in mind, Opposite's code alone is not enough to determine whether or not it will halt. It requires an input in order to determine anything. It wouldn't create a *paradox*, it just wouldn't be able to provide an answer because the code you inputted was incomplete; it doesn't run. The only problematic and potentially paradoxical scenario would be if you also provided the Input Opposite with Opposite's code, and that Input Input Opposite with Opposite's code as well, infinitely. Only then would the answer be indeterminable and self-contradictory, but that scenario is impossible to execute in reality and therefore, arguably, not very useful for determining the abilities of our computers.

> The only problematic and potentially paradoxical scenario would be if you also provided the Input Opposite with Opposite's code That is what the video and the problem is about. Its even said in the video. Opposite is given its OWN code to test. Thats the problem and thats the reason there can never be a solution to figuring out if any particular program will halt or not. Remember this is simplified, the program you would test in real life would be something much bigger with many inputs and code paths. Turing proved that computers can not solve ALL problems because this paradox exists thus if a computer can not determine if Opposite will halt or not given Opposite as its own input then that is at least 1 problem that can never be solved. The next question is, is this the ONLY problem that a computer can not solve? The problem here is as Turing proved, you cant prove a program will ever halt, so...

You just need Captain Kirk to reason logic with a computer, and it will eventually self-destruct.

Alex Turing? the guy who made the turing test? or is that another guy?

The problem precented does not quite melt human brains, now does it? Brains being computers of a type can spot the paradox and output the third choice, namely this machine is bollocks. I'd call that solved.

Alan Turing: "Hey guys. I have broken through the german code!" British government: "Why are you gay?"

I got my Comp Sci degree 30 years ago and really enjoyed this, thanks

1:13 you got me there for a sec

the hitchhiker's guide to the galaxy

our maths and computers cant..... what about aliens

"Vanishes in a puff of logic...". Thank you, Douglas Adams, wherever you are."

I would love to see a more in depth version of this video.

BBC micros

if human can't resolve a paradox, why would a computer be able solve when some thing has infinite solutions or can't reach the ultimate state using recursive it can't be solve. the world is finite but boundless count the numbers between zero and 1 try to approach zero with a function that reduce it self to zero try to count to infinite

So the answer to the question, *is* the question?

sure cant solve 0 divided by 0

Not only is impossible for a computer yo solve, it is impossible for anyone to solve.

"then it vanishes in a puff of logic" Hitchhiker's Guide reference?

This is the only channel where I am FORCED to watch the vids in 0.5x

it simply requires a subjective analysis. what the opposite box does is introduce the concept of scale. not amount, numbers, mathematics etc... SCALE this is a subjective concept that cannot be processed in absolute terms without defining 3 axis of space in order to define SCALES (which may or may not be infinite) in which to place comparative analyses, so that we may compare the recycled opposite box to the active opposite box. this is required because on/off / 0 and 1 / any binary mechanism cannot distinguish subjective data because it is not stereoscopic in it's nature. if turin had based his science on a rheostat instead of a switch we would have been using a superior alternative to binary from the outset. instead of a 'transistor' reading 0 or 1 and nothing else, thereby limiting all computers to the momentum of their absolute origins we might have had something akin to a diode which could be on, off, flowing one direction, flowing the other direction, in an alternating state with a zener buffer or in a resistive state (open at both ends) the problem with academics who focus their lives on specialization is the more specialized they become, the narrower the thinking. the qbit revolution has arrived so this is all irrelevant. we could have saved ourselves a lot of limitations in the meantime by constructing our transistor wafers as a pair of isolated circuits with semiconducting junctions forming a matrices and tailoring machine code to take advantage of this. hardware ascii if you will. in conclusion, it is not a 'problem computers cannot solve' but more a 'problem that cannot be solved by using switches, no matter how complex the circus, the limitations of the switch is fundamental' Liam

Quantum computers cannot solve the halting problem either because you can simulate a quantum computer with a turing machine. It's turing complete.

The halting problem is flawed because it's determined by an undefined initial state, ie. input. The resulting input of Opposite(Opposite(FN)) is just Halts(FN). Since FN is unknown, Halts(FN) is obviously unknown.

What is the answer to the question of life the universe and everything ?

47

47

<a href="#" class="seekto" data-time="73">1:13</a> you got me there for a sec

Alan Turing: "Hey guys. I have broken through the german code!" British government: "Why are you gay?"

When you try to solve a mathematical problem so hard that it turns into a philosophical one.

Gödel's incompleteness meme?

It can't solve its own problems

/0