1266: "Halting Problem"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

brenok
Needs Directions
Posts: 507
Joined: Mon Oct 17, 2011 5:35 pm UTC
Location: Brazil

Re: 1266: "Halting Problem"

Postby brenok » Thu Sep 19, 2013 12:39 am UTC

Arky wrote:This is possibly the most arbitrary problem I've ever come across, and one of the most pointless.

I assume you aren't very familiar with the field of Mathematics, then. Because 99% of it would possibly be more "arbitrary" or "pointless" than this.

What exactly is so strange about this problem?

rmsgrey
Posts: 3632
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

Postby rmsgrey » Thu Sep 19, 2013 2:16 am UTC

Arky wrote:Can anyone explain why the "halting problem" matters or is any different to something like "Given a description of an arbitrary mongoose, decide whether it stays a mongoose or turns into a banana"?


Obviously, it would be nice when a program on your computer stops responding to be able to tell whether you should wait (another) five minutes to see whether it recovers, or just give up on it and kill it. What the halting problem shows is that, not only do we not have a program that can tell us roughly how long any given program will take to run, we can't even have a program that would tell us whether or not any given program would ever stop, let alone how long it would take. That shows a fundamental limitation on the capabilities of computers or anything else that can be simulated by a computer.

Also, as one of the classic undecidability problems, the HP often gets used to show that another problem is impossible to solve because a solution would also solve the halting problem.


If there were a solution to the general halting problem, then it would only be interesting if the solution itself were clever or used some specific insight - it's the fact that the problem has been proven to be unsolvable that makes it interesting.

User avatar
addams
Posts: 10268
Joined: Sun Sep 12, 2010 4:44 am UTC
Location: Oregon Coast: 97444

Re: 1266: "Halting Problem"

Postby addams » Thu Sep 19, 2013 2:37 am UTC

da Doctah wrote:
player_03 wrote:Call me weird, but I consider this the most depressing comic I've read in quite a while.
You're not weird. In fact, if everybody felt like you and me, this comic would be the one that proves that XKCD does halt.

oh, dear;
there are three of us. shhh.

Spoiler:
Maybe, we are, just, being lazy.
Life is, just, an exchange of electrons; It is up to us to give it meaning.

We are all in The Gutter.
Some of us see The Gutter.
Some of us see The Stars.
by mr. Oscar Wilde.

Those that want to Know; Know.
Those that do not Know; Don't tell them.
They do terrible things to people that Tell Them.

User avatar
Pfhorrest
Posts: 5447
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 1266: "Halting Problem"

Postby Pfhorrest » Thu Sep 19, 2013 3:03 am UTC

Arky wrote:Can anyone explain why the "halting problem" matters or is any different to something like "Given a description of an arbitrary mongoose, decide whether it stays a mongoose or turns into a banana"?

It is useful to know if a program created to compute the solution to a problem will ever finish that task or will just keep trying at it forever. If you can prove that the program will eventually finish, then you know that if you just give the program enough time, you will get your answer. If you can prove that the program will never finish, then you know that it will never give you your answer and not to bother. If you can't prove it either way... then you don't know if you just need to give the program more time or if it's pointless waiting because it will never finish.

Turing proved that there is no general mechanism to prove whether a program will finish or not for any program. Which means that there are some programs which, not only do we not know if they will ever finish or not, and thus whether to bother running them, but we don't even know if there is a way to tell whether they will finish or not, because we don't and can't have a general all-purpose way of figuring that out, and there may or may not be some special way of figuring that out about this particular program (we don't know if there is until someone comes up with one).
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Thu Sep 19, 2013 5:42 am UTC

Pfhorrest wrote:How does the Halting Problem entail the Principle of Explosion?

Not the Halting Problem, but its "solution" by Randall. See below.

Arky wrote:Can anyone explain why the "halting problem" matters

For example, imagine an algorithm that gets a theorem as its input, then enumerates all finite-size proofs and halts when one is a proof of the theorem. If anybody could solve the halting problem for that particular algorithm, our logic wouldn't have Gödel's incompleteness.

Now, Randall's "solution" basically tells us that any proposition can be proven true by such an algorithm. Of course, it's not what Randall meant to do, but nonetheless.

taemyr
Posts: 111
Joined: Fri Jan 26, 2007 12:14 pm UTC

Re: 1266: "Halting Problem"

Postby taemyr » Thu Sep 19, 2013 7:44 am UTC

Kit. wrote:
Pfhorrest wrote:How does the Halting Problem entail the Principle of Explosion?

Not the Halting Problem, but its "solution" by Randall. See below.
...
Now, Randall's "solution" basically tells us that any proposition can be proven true by such an algorithm. Of course, it's not what Randall meant to do, but nonetheless.


Except that Randall's solution is not the solution to the halting problem. But rather the solution to the "big picture" halting problem; Will program p, running on an actual physical machine, stop running? The answer to which is yes, since the machine that p is running on will eventually stop running.

taemyr
Posts: 111
Joined: Fri Jan 26, 2007 12:14 pm UTC

Re: 1266: "Halting Problem"

Postby taemyr » Thu Sep 19, 2013 7:57 am UTC

Arky wrote:This is possibly the most arbitrary problem I've ever come across, and one of the most pointless.

At least "Who put the bop in she-bop-she-bop-she-bop?" has some flow to it.

Can anyone explain why the "halting problem" matters or is any different to something like "Given a description of an arbitrary mongoose, decide whether it stays a mongoose or turns into a banana"?


The halting problem is important for several reasons.

First, it's shows that there exists computational problems which are undecidable. An important result althoug one that in many ways this is premted by Gödel's incompleteness theorem. But the relation to Gödel's incompleteness theorem leads to the philosophically important Church-Turing thesis.

Second, it's an example of an undecidable computational problem. This allows us to show that other problems are undecidable as well. We can do this by showing that if we can decide instances of problem p we could use that solution to decide the halting problem. For example this tells us that the following problem is undecidable; "Given a program, p, will p ever exhibit behaivour foo?" This means that a perfect malware detector is impossible. And also that it's impossible to prove in general that your program correctly implements a given specification.

Third the question of wether a program halts can be interesting on it's own. For example if a program is in a long loop, tying up your system resources. It would be nice if the OS could inspect the system and decide if said program would finish whatever it's currently doing or not. - And kill it if the program would never produce output or wait for input. Ie. will the current part of said program ever halt? But that is sadly not possible.

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Thu Sep 19, 2013 8:05 am UTC

taemyr wrote:Except that Randall's solution is not the solution to the halting problem. But rather the solution to the "big picture" halting problem;

So, in short, it's a bobcat.

LockeZ
Posts: 51
Joined: Mon Jan 19, 2009 8:30 am UTC

Re: 1266: "Halting Problem"

Postby LockeZ » Thu Sep 19, 2013 8:48 am UTC

I don't really know what this comic is about, but I'm like 80% sure it's related to Will It Blend?

hyperpape
Posts: 5
Joined: Wed Jan 11, 2012 12:55 pm UTC

Re: 1266: "Halting Problem"

Postby hyperpape » Thu Sep 19, 2013 1:26 pm UTC

What other people have said is a good explanation of the importance of the halting problem, but it goes further than that. For the same reasons that the halting problem is unsolvable, it's impossible to prove that any non-trivial property of a program holds: you cannot decide whether a given program will print lines, will delete your hard-drive, etc, etc.

The basic idea behind the proof:

Code: Select all

function main () {
    doSomethingReallyComplicatedThatMightNotHalt();
    deleteYourHardDrive();
}


Since you can't decide if the first line halts, you can't decide if your hard-drive will be deleted.

That's contrived, but for the same reason, you don't know whether this program will just print some output or delete a bunch of files--it depends on the value of the first calculation:

Code: Select all

function main () {
    a = doAComplexCalculation();
    decideWhichActionToTakeBasedOnAValue(a);
}


If you replace the function "doAComplexCalculation" with "doASimpleCalculation", you may be able to guarantee that a will only ever take safe values, but there are things you can't do with "simple" calculations.

So there is a fundamental trade off between your ability to say whatever you want in a programming language, and your ability to guarantee that the program does what you expect it to do.

Some languages, like Python, are extremely flexible, at the cost of lacking guarantees about the behavior of your program. You cannot write a program that reliably tells you if a Python program writes to disk. If it's simple enough, you may be able to tell, but if it does sufficiently complicated things, you cannot statically analyze it to determine what it does.

Some languages, like Haskell, give you very strong guarantees that certain types of errors are impossible: either the program will not compile, or if it does compile, it will behave in specific ways (specifically, various functions have types that tell you whether they produce numbers or not, can write to disk or not, etc).

Even more restrictive languages such as Agda escape the halting problem by only allowing you to write programs that terminate. But there are valuable programs that you can't write in Agda: you cannot write an interpreter for Python or Haskell in Agda, because a program written in Python or Haskell might not halt, and therefore the interpreter might not halt.

What the halting problem and its extensions tell us is that while we can try to develop better tools, we will never escape the tradeoff between expressiveness and safety.

User avatar
Shidoshi
Posts: 84
Joined: Thu Jul 21, 2011 9:21 am UTC
Location: Brazil - Porto Alegre

Re: 1266: "Halting Problem"

Postby Shidoshi » Thu Sep 19, 2013 2:31 pm UTC

This topic, more than comic itself, has made me wiser. For that I thank you Computer Science XKCDers.

rmsgrey
Posts: 3632
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

Postby rmsgrey » Thu Sep 19, 2013 5:18 pm UTC

hyperpape wrote:Since you can't decide if the first line halts, you can't decide if your hard-drive will be deleted.


What you can do is detect whether the program includes the instruction to delete your hard drive (if it doesn't, then it probably won't delete your hard drive; if it does, then it might or might not).

Of course, then you get programs which modify their own code while running, or which don't technically delete your hard drive, but rather overwrite it with random characters, or delete every file on it or...

So, yeah, you can say that a given program definitely will wipe your hard drive, that a given program has the potential to, but you can't be sure, or that a given program should be safe unless it's doing something very clever (or very stupid) - a friend once wrote a program that included a flood-fill routine that didn't treat the screen edges as boundaries, so the program tried to colour the entire memory blue...

User avatar
ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 1266: "Halting Problem"

Postby ucim » Thu Sep 19, 2013 6:39 pm UTC

rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive
... but you cannot detect whether the program includes instructions for creating and then executing instructions that delete your hard drive. It's the complex part in the middle that makes it hard.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

rmsgrey
Posts: 3632
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

Postby rmsgrey » Thu Sep 19, 2013 8:57 pm UTC

ucim wrote:
rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive
... but you cannot detect whether the program includes instructions for creating and then executing instructions that delete your hard drive. It's the complex part in the middle that makes it hard.

Jose


Yeah, I'd class that under "modify their own code while running"

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Thu Sep 19, 2013 9:41 pm UTC

rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive

Which language has such an instruction?

rmsgrey
Posts: 3632
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

Postby rmsgrey » Thu Sep 19, 2013 10:49 pm UTC

Kit. wrote:
rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive

Which language has such an instruction?


Visual Basic, C# and presumably other .NET languages allow you to pass shell commands to the Windows operating system - like "format c:"

I'd have to look up the exact commands, but I could easily write a program that would try to wipe the OS partition - I would expect it to crash rather than complete since several of the files would be open and write-protected, but I wouldn't be surprised if it left Windows in a seriously corrupted state. Wiping a partition that isn't the one from which the OS is currently running would be easy (though it might take me a couple of tries to get it right) - I assume Windows actually has some protections against users deleting the running OS - though obviously since it's designed to allow updating, there will be ways of doing it.

There are legitimate reasons for wanting to be able to read, write, create and delete files and directories from within a program, so a competent programming language will offer at least that level of disc access. Actually reformatting a drive is something that should be pretty rare, so, while it's possible, it's something that a competent programming language is unlikely to make easy to do...

User avatar
ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 1266: "Halting Problem"

Postby ucim » Fri Sep 20, 2013 12:30 am UTC

rmsgrey wrote:
ucim wrote:
rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive
... but you cannot detect whether the program includes instructions for creating and then executing instructions that delete your hard drive. It's the complex part in the middle that makes it hard.

Yeah, I'd class that under "modify their own code while running"
Doesn't even have to be that. Programs can, without modifying themselves, run code that is stored in files. They can write files, nothing says they can't write the files they will execute. They can write the command to delete your hard drive to that file, but do it in pieces so it's not obvious in the code.

Sure, you can write a program to detect that too, if you're clever enough. But you'll never know if the other programmer was more clever, or otherwise, if the program simply won't delete your hard drive in the first place.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

rmsgrey
Posts: 3632
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

Postby rmsgrey » Fri Sep 20, 2013 12:48 am UTC

ucim wrote:
rmsgrey wrote:
ucim wrote:
rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive
... but you cannot detect whether the program includes instructions for creating and then executing instructions that delete your hard drive. It's the complex part in the middle that makes it hard.

Yeah, I'd class that under "modify their own code while running"
Doesn't even have to be that. Programs can, without modifying themselves, run code that is stored in files. They can write files, nothing says they can't write the files they will execute. They can write the command to delete your hard drive to that file, but do it in pieces so it's not obvious in the code.

Sure, you can write a program to detect that too, if you're clever enough. But you'll never know if the other programmer was more clever, or otherwise, if the program simply won't delete your hard drive in the first place.

Jose


You're equivocating on the definition of "program" here - if it's the program that wipes your hard drive, then you can't say that the executable it creates and runs that actually wipes your hard drive isn't part of the program. Either the code that executes to wipe your hard drive is part of the program (and in this case was modified by the program while it was running) or it's not part of the program, and the program didn't wipe your hard drive.

What you can, in principle, detect is whether the program is capable of changing the code that could be executed while running, or just choosing among existing code to execute - if the latter, and none of the existing code includes the instruction to wipe the hard drive, you're probably safe.

User avatar
Darekun
Posts: 38
Joined: Thu Jan 03, 2013 7:57 am UTC

Re: 1266: "Halting Problem"

Postby Darekun » Fri Sep 20, 2013 12:50 am UTC

rmsgrey wrote:Visual Basic, C# and presumably other .NET languages allow you to pass shell commands to the Windows operating system - like "format c:"

That's a… decidedly DOS-y way to do it under Windows. But, assuming you're using shell commands instead of IOCTLs, what about a program that has an edit where the user types a shell command? What about a program that accepts a text file, builds a sort of hash, and uses that as a shell command?

What about a program that sets itself to run at boot, and uses the last 256 bytes of %SystemRoot%\WindowsUpdate.log to seed a PRNG, and uses that to generate a shell command?

Then you'd have a program that does all sorts of strange things, most of which harmlessly return errors, but probably some of which are nasty. With a weak PRNG, it might or might not be able to delete your hard drive(at least as well as DEL deletes files), and it might only be able to do it if the log entries from Windows are in Korean or something. Even if you had the source, you'd basically have to run it in a sandbox with a variety of log files to see if it can delete your hard drive, and it doesn't have the word "format" in it anywhere.

And, of course, it could include something kind of like a cryptographic salt, which on Windows installs of a particular language restricts it to a set of harmless and amusing things. So it's "clearly" intended as a programmer toy, not a weapon aimed at Korea.

(And if your company's products run on Windows and you deal with a significant number of asian customers, you may find that last hypothetical program disturbingly close to accidents that actually happen.)



More generally, it's not that the halting problem's important to computers as we know them, it's that a solution to it is necessary for a bunch of computer stuff we'd like to have, and can't. The concept of Turing completeness would be fluid if the halting problem were solvable. It's the programming equivalent of political science spending a few hundred years trying to build a trustworthy legal system that runs on humans, before determining that it can't be done and we'll have to muddle along until we can upgrade the humans enough.

User avatar
Biliboy
Posts: 284
Joined: Tue Jun 24, 2008 6:43 am UTC

Re: 1266: "Halting Problem"

Postby Biliboy » Fri Sep 20, 2013 1:28 am UTC

Wouldn't another way of putting this problem be:

The outcomes of processes cannot be deduced without running either the process itself or an equally complex simulation of that process.

If so, it seems... common-sensical? If I write

10 Print "Hi"
20 End

then you don't know what that program will do, unless you run it, or, in your mind, run a simulation based on your knowledge of outdated programming languages.

Scale that up to whatever size you like. If it were any other way, I'd be making a living as a prophet, skipping those humdrum intermediate steps everyone else has to go through to find things out, like, you know, living 20 years.

User avatar
ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 1266: "Halting Problem"

Postby ucim » Fri Sep 20, 2013 4:39 am UTC

rmsgrey wrote:You're equivocating on the definition of "program" here - if it's the program that wipes your hard drive, then you can't say that the executable it creates and runs that actually wipes your hard drive isn't part of the program.
I'm not saying that. It most certainly is "the program" that wipes the hard drive. It just does so in a way that's hard to detect by examining the source code. What the completeness problem implies is that a program can be written where it's harder to figure out whether or not it can wipe the hard drive than it is to simply run the program and see what it does, and in that case, if the program takes an arbitrarily long time to get to that point, the only way to know that it will in fact do so is to wait for it.

You might wait forever and still not know. There are no shortcuts in a case like that. And you may not know if you are in a case like that.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Fri Sep 20, 2013 11:14 am UTC

rmsgrey wrote:
Kit. wrote:
rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive

Which language has such an instruction?

Visual Basic, C# and presumably other .NET languages allow you to pass shell commands to the Windows operating system - like "format c:"

An ability to pass shell commands (which basically any good text editor program, for example, needs to have) is not a detectable instruction to delete a hard drive.

rmsgrey wrote:I'd have to look up the exact commands, but I could easily write a program that would try to wipe the OS partition - I would expect it to crash rather than complete since several of the files would be open and write-protected, but I wouldn't be surprised if it left Windows in a seriously corrupted state.

Before Vista, you could do it using just CreateFile()/WriteFile(). Good luck statically detecting that without false-positives.

With Vista and later Windows, you need help from a device driver to wipe a mounted filesystem.

Biliboy wrote:If so, it seems... common-sensical? If I write

10 Print "Hi"
20 End

then you don't know what that program will do, unless you run it, or, in your mind, run a simulation based on your knowledge of outdated programming languages.

Scale that up to whatever size you like.

Not really.

10 FOR F$ = 1 TO 10000
20 PRINT "Hi!"
30 NEXT F$
40 PRINT "Bye!"

I don't need to "run" all 10000 iterations in my mind to know what is supposed to happen.

rmsgrey
Posts: 3632
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

Postby rmsgrey » Fri Sep 20, 2013 1:31 pm UTC

ucim wrote:
rmsgrey wrote:You're equivocating on the definition of "program" here - if it's the program that wipes your hard drive, then you can't say that the executable it creates and runs that actually wipes your hard drive isn't part of the program.
I'm not saying that. It most certainly is "the program" that wipes the hard drive. It just does so in a way that's hard to detect by examining the source code. What the completeness problem implies is that a program can be written where it's harder to figure out whether or not it can wipe the hard drive than it is to simply run the program and see what it does, and in that case, if the program takes an arbitrarily long time to get to that point, the only way to know that it will in fact do so is to wait for it.

You might wait forever and still not know. There are no shortcuts in a case like that. And you may not know if you are in a case like that.

Jose


What I'm saying is that it is possible to algorithmically partition programs into three classes - ones that (provided your algorithm is correct) won't wipe your hard drive, ones that will wipe your hard drive, and ones that might or might not and need further study to determine. Depending on how seriously you take the Church-Turing thesis, there may well be examples in the third category that are impossible for humans to decide on too...

***

Another interesting consequence of the Halting Problem is that it's impossible to program a computer capable of analysing automated subway systems that can decide for any arbitrary system whether or not a given train will end up at a given station... (proof: design a subway system that simulates a Turing machine)

User avatar
orthogon
Posts: 3078
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1266: "Halting Problem"

Postby orthogon » Fri Sep 20, 2013 1:48 pm UTC

Kit. wrote:
rmsgrey wrote:What you can do is detect whether the program includes the instruction to delete your hard drive

Which language has such an instruction?

Bah, any language that doesn't have such an instruction is for wimps and beginners.

More advanced languages have instructions like such as "add operand 1 to operand 2, store the result in operand 3 and wipe hard drive on overflow".

Even these instructions are relatively benign in their possible side-effects compared to GOTO.

Hence, a corollary of the halting problem that it's impossible to tell for an arbitrary program whether it will result in raptor attack.
xtifr wrote:... and orthogon merely sounds undecided.

User avatar
Biliboy
Posts: 284
Joined: Tue Jun 24, 2008 6:43 am UTC

Re: 1266: "Halting Problem"

Postby Biliboy » Fri Sep 20, 2013 3:57 pm UTC


Biliboy wrote:If so, it seems... common-sensical? If I write

10 Print "Hi"
20 End

then you don't know what that program will do, unless you run it, or, in your mind, run a simulation based on your knowledge of outdated programming languages.

Scale that up to whatever size you like.

Not really.

10 FOR F$ = 1 TO 10000
20 PRINT "Hi!"
30 NEXT F$
40 PRINT "Bye!"

I don't need to "run" all 10000 iterations in my mind to know what is supposed to happen.


But you do, that's what I'm saying. You look at that, and literally cannot know what will happen just by looking at it. Your brain processes it, simulates the results, even if it does not actually go through each of the 10,000 iterations the way a computer would. I'm saying that that brain simulation is necessarily equally complex. (Note: I'm not a programmer, that much Basic is about all I can parse, so nothing more complex please)

This 'halting problem' is one of those things that is either so entirely basic that it's genius, or not worth worrying about at all. I still haven't decided which.

User avatar
ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 1266: "Halting Problem"

Postby ucim » Fri Sep 20, 2013 5:20 pm UTC

rmsgrey wrote:What I'm saying is that it is possible to algorithmically partition programs into three classes - ones that (provided your algorithm is correct) won't wipe your hard drive, ones that will wipe your hard drive, and ones that might or might not and need further study to determine. Depending on how seriously you take the Church-Turing thesis, there may well be examples in the third category that are impossible for humans to decide on too...
Agreed. Like close encounters, it's the third type which makes life interesting.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Fri Sep 20, 2013 5:27 pm UTC

Biliboy wrote:But you do, that's what I'm saying. You look at that, and literally cannot know what will happen just by looking at it. Your brain processes it, simulates the results, even if it does not actually go through each of the 10,000 iterations the way a computer would. I'm saying that that brain simulation is necessarily equally complex. (Note: I'm not a programmer, that much Basic is about all I can parse, so nothing more complex please)

Well, is

Code: Select all

main() {
  for(;;);
  return 0;
}

simple enough for you to parse?

Would it take you forever to find out that it will never "return 0"?

Oktalist
Posts: 79
Joined: Thu Apr 22, 2010 10:13 pm UTC

Re: 1266: "Halting Problem"

Postby Oktalist » Mon Sep 23, 2013 4:18 pm UTC

Arky wrote:This is possibly the most arbitrary problem I've ever come across, and one of the most pointless.

Considering that it was this very problem which led Turing to formulate the notion of a computing machine, I'd say that the above proposition was possibly the most wrong of any I've ever come across on the Internet.
philip1201 wrote:Not everything which maps countable infinities onto finite areas is a Lovecraft reference.

Oktalist
Posts: 79
Joined: Thu Apr 22, 2010 10:13 pm UTC

Re: 1266: "Halting Problem"

Postby Oktalist » Mon Sep 23, 2013 4:40 pm UTC

Biliboy wrote:Wouldn't another way of putting this problem be:

The outcomes of processes cannot be deduced without running either the process itself or an equally complex simulation of that process.[/i]

No. There are some programs whose outputs cannot be deduced even by running them (or a simulation of them, which is the same thing).

it seems... common-sensical?

If that is the case, then it is only due to the people who came before us who overturned prior common sense, which held that the opposite was true.
philip1201 wrote:Not everything which maps countable infinities onto finite areas is a Lovecraft reference.

User avatar
Pfhorrest
Posts: 5447
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 1266: "Halting Problem"

Postby Pfhorrest » Mon Sep 23, 2013 11:14 pm UTC

Oktalist wrote:There are some programs whose outputs cannot be deduced even by running them (or a simulation of them, which is the same thing).

Only ones that really don't halt. The ones that do halt, you just have to let them run long enough and eventually you'll know.

The problem is in telling ahead of time whether there is such a thing as "let it run long enough" for a given program, or if you'd be pointlessly waiting forever.
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

Zinho
Posts: 102
Joined: Fri Apr 08, 2011 3:23 pm UTC

Re: 1266: "Halting Problem"

Postby Zinho » Tue Sep 24, 2013 5:59 pm UTC

Pfhorrest wrote:
Oktalist wrote:There are some programs whose outputs cannot be deduced even by running them (or a simulation of them, which is the same thing).

Only ones that really don't halt. The ones that do halt, you just have to let them run long enough and eventually you'll know.

The problem is in telling ahead of time whether there is such a thing as "let it run long enough" for a given program, or if you'd be pointlessly waiting forever.

There have been lots of requests for explanations of the joke in the comic, and I think Pfhorrest has come the closest of anyone I've read so far. Here's my summary for those who still haven't got it:

<spoiling_the_joke>
Randall's pseudocode here suggests a practical, "big-picture" solution to Turing's Halting Problem: run the program and see. Ultimately, the "big picture" is a tautological "you know that it will halt when it halts". Honestly, you know you're going to run it anyways, so why worry?

I find this funny because it subverts one of the original assumptions of the halting problem, namely that the program hasn't run yet and you're trying to determine whether it will. Executing Randall's test code will only give an answer after the answer is already known, so it's useless for solving the general problem. I also think this is an example of Randall trolling comp-sci nerds, and trolling is funny (for the troll); from the comments so far I think it's working.
</spoiling_the_joke>

Now, can someone please explain the title-text? Several posters have suggested that Randall's counterexample is God (as in "I found God"), and that Randall can't show anyone because he hasn't found a reliable way to summon God in the interest of Science. Should I stop looking further than that for a meaning in the title text?

Oktalist
Posts: 79
Joined: Thu Apr 22, 2010 10:13 pm UTC

Re: 1266: "Halting Problem"

Postby Oktalist » Tue Sep 24, 2013 6:10 pm UTC

That's not what the psuedo-code says at all. The "big picture solution" doesn't run the program. It simply returns true no matter what program is passed to it, because in the end all programs will halt.
Last edited by Oktalist on Tue Sep 24, 2013 9:42 pm UTC, edited 1 time in total.
philip1201 wrote:Not everything which maps countable infinities onto finite areas is a Lovecraft reference.

Zinho
Posts: 102
Joined: Fri Apr 08, 2011 3:23 pm UTC

Re: 1266: "Halting Problem"

Postby Zinho » Tue Sep 24, 2013 8:49 pm UTC

Oktalist wrote:That's not what the psuedo-code says at all. The "big picture solution" doesn't run the program. It simply returns true no matter what program is passed to it, because in the end all programs will halt. This was already explained by the second post in this thread.

What you're proposing is just restating the original problem.

:oops: You're right, I mis-read the pseudocode; I thought Randall was evaluating the output of the function instead of the code of the function itself. If he meant what I thought he'd have written DoesItHalt( program() ). Reading comprehension fail for me :x

User avatar
Znirk
Posts: 174
Joined: Mon Jul 01, 2013 9:47 am UTC
Location: ZZ9 plural Z α

Re: 1266: "Halting Problem"

Postby Znirk » Wed Sep 25, 2013 1:45 pm UTC

Kit. wrote:
Biliboy wrote:But you do, that's what I'm saying. You look at that, and literally cannot know what will happen just by looking at it. Your brain processes it, simulates the results, even if it does not actually go through each of the 10,000 iterations the way a computer would. I'm saying that that brain simulation is necessarily equally complex. (Note: I'm not a programmer, that much Basic is about all I can parse, so nothing more complex please)

Well, is

Code: Select all

main() {
  for(;;);
  return 0;
}

simple enough for you to parse?

Would it take you forever to find out that it will never "return 0"?

I'm not technically the person you asked, but in a similar situation (I speak rudiments of BASIC and Scheme).

It would take my looking up some language documentation (and of course it would help if I knew what language this is). Just from looking at it? No chance. Too many semicolons doing (presumably) different things, not enough clues on what "main" and "for" do, exactly.

Does "return" define the value of the function? I sort of get that from the way you ask the question, but again I wouldn't necessarily have gotten there unaided.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: 1266: "Halting Problem"

Postby Xenomortis » Wed Sep 25, 2013 2:33 pm UTC

Kit. wrote:Well, is

Code: Select all

main() {
  for(;;);
  return 0;
}

simple enough for you to parse?

Would it take you forever to find out that it will never "return 0"?

Given C++*, here is a valid interpretation of your program.

Code: Select all

main(){
  return 0;
}

Actually, depending on how you interpret the spec, your code is either defined and terminates, or is undefined and therefore nonsensical (remember, a language is defined w.r.t to an abstract machine, not a real one).
It just so happens that most compilers do the dumb thing.

*Less sure on C
Image

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Wed Sep 25, 2013 3:17 pm UTC

Znirk wrote:I'm not technically the person you asked, but in a similar situation (I speak rudiments of BASIC and Scheme).

Code: Select all

10 GOTO 10
20 PRINT "Goodbye"

Code: Select all

(define (whatever n)
  (if (zero? n)
    "Bye!"
    (whatever n)))

(whatever 1)

Znirk wrote:It would take my looking up some language documentation (and of course it would help if I knew what language this is).

It wouldn't take you infinite time, wouldn't it?

Xenomortis wrote:Given C++*, here is a valid interpretation of your program.

Code: Select all

main(){
  return 0;
}

Not according to ISO/IEC 14882:1998, where it's equivalent to a completely different:

Code: Select all

main(){
label:
  goto label;
  return 0;
}

Or have they changed this in a more recent standard?

Xenomortis wrote:Actually, depending on how you interpret the spec,

I suggest to interpret it literally. I.e. if there is no way for the flow of control to reach "return 0", it's not called. See 1.9.5 of the ISO/IEC 14882:1998.

Xenomortis wrote:your code is either defined and terminates, or is undefined and therefore nonsensical (remember, a language is defined w.r.t to an abstract machine, not a real one).

I couldn't find the word "nonsensical" in the Standard. I also see no behavior in this code that wouldn't be defined by the Standard.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: 1266: "Halting Problem"

Postby Xenomortis » Wed Sep 25, 2013 3:59 pm UTC

Turns out I was reading an out of date draft (2010, not 2011). The relevant section was 6.5.0, but it's been changed. It said:
A loop that, outside of the for-init-statement in the case of a for statement,
— makes no calls to library I/O functions, and
— does not access or modify volatile objects, and
— performs no synchronization operations (1.10) or atomic operations (Clause 29)
may be assumed by the implementation to terminate.

It doesn't say this now.

Kit. wrote:I couldn't find the word "nonsensical" in the Standard. I also see no behavior in this code that wouldn't be defined by the Standard.

In the strictest sense, code that is undefined is nonsensical; it is devoid of meaning.

Kit. wrote:I suggest to interpret it literally.

Sure. But supposing the spec wasn't changed, what would the literal interpretation be? The spec says the compiler is allowed to assume the loop terminates, not that it has to. In that case, the program isn't well defined.
(This is hypothetical now and likely detracts from the point of the thread.)
Image

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1266: "Halting Problem"

Postby Kit. » Wed Sep 25, 2013 4:31 pm UTC

Xenomortis wrote:But supposing the spec wasn't changed, what would the literal interpretation be? The spec says the compiler is allowed to assume the loop terminates, not that it has to. In that case, the program isn't well defined.
(This is hypothetical now and likely detracts from the point of the thread.)

Then Randall's "big picture" solution would be completely legit for any Turing machine interpreter written in C++ and not using library I/O inside its main loop.

User avatar
Darekun
Posts: 38
Joined: Thu Jan 03, 2013 7:57 am UTC

Re: 1266: "Halting Problem"

Postby Darekun » Thu Sep 26, 2013 4:39 am UTC

How about this:

Code: Select all

int main()
{
   for ( byte I = 0; I < 200; ++I )
      pConsole[I % 20][I / 20] = 0x0730 + (I % 10)
   ;
   return 0;
}

where byte³ is signed¹, and pConsole points to volatile²?

¹ And therefore -128..127, to the presumed surprise of the programmer.
² Specifically, the VGA text-mode display.
³ Why isn't there [tt]inline fixed-width[/tt]?

User avatar
Znirk
Posts: 174
Joined: Mon Jul 01, 2013 9:47 am UTC
Location: ZZ9 plural Z α

Re: 1266: "Halting Problem"

Postby Znirk » Thu Sep 26, 2013 11:22 am UTC

Kit. wrote:
Znirk wrote:It would take my looking up some language documentation (and of course it would help if I knew what language this is).

It wouldn't take you infinite time, wouldn't it?

Unlikely, but as I read it the conversation had shifted to "Is this simple enough for you to parse" (implicitly with no other sources of information).

Will it take you and xenomortis infinite time to agree on what it means?


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: colonel_hack, PM 2Ring and 41 guests