How do you define “contains it”?

@chaumas Contains a machine that has an effect on any of its logic.

@ _Any_ of its logic? That would be all machines. Which is false, of course, because a machine can solve the halting problem for certain subsets of machines.

@chaumas Okay, that was a bit too loosely worded. My point is that no machine can solve the halting problem with a definite and correct answer if it is requested to solve the problem with a compound machine that uses it in any of its processing.

@@XNorYT The problem is that unless you can define what you mean by that precisely, there’s not a lot we can say about it. However, just going by an intuitive interpretation, say we build a machine like X, but we replace N with a machine that doesn’t negate, and instead just does whatever H says. Now _any_ implementation of H that gives either answer will always correctly answer the halting problem for this case, even though this machine contains a full on copy of H. So your statement, just going by an intuitive interpretation doesn’t seem to be true.

If H gives the opposite answer, then that answer will also be wrong. No matter what, X will do the opposite of what H says, so H can’t get the answer right.

Omg no way its chaumus I heard a lot about you in the comment section

There is never "no correct output" for H. Machines either run forever or they don't. There is no third option.

@chaumas H will receive the blueprint for X and simulate it, then the simulation simulates it and the simulation of the simulation will simulate it, then the simulation of the simulation of the simulation simulates it, and so on forever, causing H, to take an infinite amount of time (and RAM space) to process it. And since the only correct answer to "Will the next word you say be no?" is never saying anything ever again, X's output would technically be correct.

@chaumas I guess you're right, there is no option that is both 0 and 1... Wait... QUANTUM COMPUTERS HAVE QBITS THAT CAN BE BOTH 0 AND 1 AT THE SAME TIME! H WAS A QUANTUM COMPUTER ALL ALONG!

Then it wouldn't fit the definition of H.

The only quibble I have with your comment is the claim that you’d become rich. Our society doesn’t value academic contributions that much. You’d for sure get your name in a textbook though.

@@chaumas I was thinking about that. Maybe a better strategy would be to show it to a private company under an NDA and agree to license it to them for a royalty? I imagine Google, Amazon, etc. would be willing to pay any amount of money for something like this, but also I don't know how copyrightable/trademarkable a proof is. Or maybe you could figure out P = NP from this somehow and claim the Millenium Prize.

We don't have an ocean on the moon. Who said life was fair.

@@wavydaveyparker lol

It all depends on which reference frame you're using. If a cop used an excessive fictitious force, then that would imply that you were accelerating, and they could claim that they were at rest, and you put the cuffs on yourself.

@@wavydaveyparker they could claim I committed a fictitious crime.

That all depends on which reference court the case hearing was being held. In the inertial court, there was no crime - And you'd get off scot-free! If however, we were in the non-inertial courtroom - then your honour, 👩‍⚖️ the defendant is guilty of fictitious charges. And you're going down, I'm sorry too say.

@ that’s funny

LLMs can't solve the Halting Problem either.

In this specific case we want to show that, when just limiting to "Halts" or "Does not halt", the machine cannot give a logically plausible answer. Which does not make sense, as intuitively every machine either holds or not. There is no "inbetween" super position of halting and not halting at the same time. A machine either halts, or it doesn't. The interesting result is: You can define for every machine M a set of inputs T for which M halts, and a set of inputs ⊥ for which M does not halt. But: It is impossible to create a single machine H which correctly evalutes for an arbitrary machine M and input I whether M on I halts, or not. And there is no inbetween. The example in the video shows, though, that it is impossible to say for a machine with logical consistency whether this specific input halts. It shows that Computers are *unable* to say with correctness whether an arbitrary program halts or not, because Computers are logically unable to do so

Can you define precisely when your version of H gives that “exception” output?

How would you know if H is permanently stuck or just needs some more, finite, time to give the answer?

The problem is that “when it can’t have the right answer” isn’t possible for a machine to determine. Let’s be specific: we have a machine we’ll call “Almost H”, or AH which often answers the halting problem correctly, but sometimes gets it wrong. We want to build a second machine we’ll call “Check Almost H” or CAH which returns true if AH would give the right answer, and false otherwise. Well, here’s the issue. I can build this machine now 1. Pass blueprint and input to AH to get “initial answer” 2. Pass blueprint and input to CAH to check AH 3. If CAH said true, return the initial answer 4. Otherwise return the opposite of the initial answer And oops, I just built H, which is impossible. So CAH must also be impossible. The upshot is that yes, you can build partial halting solvers, but they must either give the wrong answer in an infinite number of cases (and we can’t tell which they are), or it must give a non-answer in an infinite number of cases, some of which are halting cases and some of which are non-halting cases. A key point here is that there is no such thing as an individual machine and input whose halting answer is undecidable. Either a machine that always says “stuck” or a machine that always says “not stuck” will get the answer right for a given case. It’s when we try to build a single machine that gets it right in _every_ case that we hit a contradiction.

So... your solution is to ignore the problem?

@@paulblart7378 yeah! just use machines in the way they're intended. they may not be able to do *everything*, but if you're gonna use them don't torture them ._.

@@goldfishglory ...I guess that makes sense. That has no relevance to this proof though.

No, H is not an emulator. An emulator takes in a description of a machine and an input and does whatever the machine would have done with the input. If the described machine doesn't halt, the emulator doesn't halt. If the emulator halts, you know that the machine described will halt. If the emulator _doesn't_ halt, you can't tell the difference between "hasn't halted yet" and "won't ever halt". H is different. It takes a description of a machine and an input, and _tells you_ whether the machine described will ever halt. This is a completely different task from emulation. For example, take this machine: 1. Take in a number as an input 2. If the input is even, print out a billion smiley faces and then halt 3. Otherwise, print out a billion frowny faces and go to step 2 Now, does this machine halt if we feed it "7" as an input? No. In this specific case, we can see that instantly, and we didn't have to emulate anything. We can figure out the answer without writing down a single frowny face, much less a billion. But if you feed that description to an emulator and give it the number 7, the emulator will never tell us whether the program halts. It will just keep printing out frowny faces forever.

@@chaumas ...fair enough.

No, it's not like that. Dividing by zero is not defined. A calculator that prints out "undefined" or "error" when you try to divide by zero is not a contradiction; it is behaving correctly according to its definition. The question of whether a machine halts on a given input _is_ always defined. It always has a single, concrete answer. But when we imagine a machine capable of consistently _finding_ that answer, we see a contradiction.

lemme edit the comment so its more defined

That function (or in this case, machine) needs 2 inputs. You can't say "use the input that you already have", usually.