1266: "Halting Problem"

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

Moderators: Moderators General, Prelates, Magistrates

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

1266: "Halting Problem"

Postby Demki » Wed Sep 18, 2013 4:15 am UTC

Image

Title text: "I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone."

What about while(true){}?

jasper.a.visser
Posts: 4
Joined: Wed Sep 18, 2013 4:24 am UTC

Re: 1266: "Halting Problem"

Postby jasper.a.visser » Wed Sep 18, 2013 4:25 am UTC

Considering that every computer you ever build will cease to function (even if it lasts until the heat death of the universe), yes, while(true) {} will halt.

Istaro
Posts: 101
Joined: Mon Jan 05, 2009 6:00 pm UTC

Re: 1266: "Halting Problem"

Postby Istaro » Wed Sep 18, 2013 4:33 am UTC

Demki wrote:What about while(true){}?


Well . . . heat death of the universe?

Edit: Interesting. When I posted this, it was the second post, and it still was an hour or so later when I refreshed, but when I came back again many hours later, an intervening post had appeared.
Last edited by Istaro on Wed Sep 18, 2013 10:29 am UTC, edited 1 time in total.

User avatar
TimXCampbell
Posts: 110
Joined: Wed Jul 27, 2011 4:26 am UTC
Location: Very Eastern Kentucky, USA
Contact:

Re: 1266: "Halting Problem"

Postby TimXCampbell » Wed Sep 18, 2013 4:43 am UTC

Code: Select all

While Not DoesItHalt(Do While True) Print 'Not Yet'
Print 'It halted!'

I guess I'd need a really, really big UPS for the program above to make some kind of statement.

Antior
Posts: 61
Joined: Wed Jan 18, 2012 10:34 pm UTC

Re: 1266: "Halting Problem"

Postby Antior » Wed Sep 18, 2013 5:25 am UTC

For those who aren't as nerdy as some of you, here's the Wikipedia definition of the Halting Problem:

Wikipedia wrote:In computability theory, the halting problem can be stated as follows: "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever". This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, what became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: 1266: "Halting Problem"

Postby Cauchy » Wed Sep 18, 2013 5:42 am UTC

I'm apparently not nerdy enough to know what a "big picture solution" is.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Harry Voyager
Posts: 52
Joined: Thu Nov 04, 2010 7:55 am UTC

Re: 1266: "Halting Problem"

Postby Harry Voyager » Wed Sep 18, 2013 5:54 am UTC

My understanding was the real problem of the halting problem was understanding how long it would take the process to reach a natural conclusion. Halting a problem by hitting it with a baseball bat is more the trivial solution. Granted, sufficient force will solve most problems, but the side effects may not be entirely desirable.

User avatar
The Chosen One
Posts: 34
Joined: Mon Mar 08, 2010 8:21 am UTC

Re: 1266: "Halting Problem"

Postby The Chosen One » Wed Sep 18, 2013 6:03 am UTC

With regards to the title text, though, there are a few billion potential witnesses...
"Strictly speaking, the observed death rate for the human condition is something like 93%"
If you ever find yourself asking, "is the answer to the question, "is the answer to the question, "am I the only one?" no?" no?" The answer is still no, but you should probably close all those Logic Puzzles tabs and go to sleep.

User avatar
keithl
Posts: 660
Joined: Mon Aug 01, 2011 3:46 pm UTC

Re: 1266: "Halting Problem"

Postby keithl » Wed Sep 18, 2013 6:27 am UTC

I knew a guy named Harold Ting. He had a problem.

DBPZ
Posts: 28
Joined: Mon Aug 31, 2009 5:17 am UTC

Re: 1266: "Halting Problem"

Postby DBPZ » Wed Sep 18, 2013 6:29 am UTC

Code: Select all

from oracle import TheUniverseIsCollapsing

def DoesItHalt (program):
    while not TheUniverseIsCollapsing():
        pass
    return 1


fr00t
Posts: 113
Joined: Wed Jul 15, 2009 11:06 am UTC

Re: 1266: "Halting Problem"

Postby fr00t » Wed Sep 18, 2013 6:35 am UTC

Cauchy wrote:I'm apparently not nerdy enough to know what a "big picture solution" is.


Well theoretically there is no general solution to the halting problem, but that refers to computations which are not limited by practical considerations such as finite memory (as in physics: http://xkcd.com/669/). In the real world of course, any computation is going to halt for one reason or another, perhaps by heat death of the universe if it comes to it (but it won't).

Or am I missing something?

User avatar
TimXCampbell
Posts: 110
Joined: Wed Jul 27, 2011 4:26 am UTC
Location: Very Eastern Kentucky, USA
Contact:

Re: 1266: "Halting Problem"

Postby TimXCampbell » Wed Sep 18, 2013 6:47 am UTC

fr00t wrote:Or am I missing something?

Maybe. If the acceleration of the universe is, in fact, an illusion, and the universe will go back to a Big Crunch, which is followed by an identical universe (or a return to the same time), then the program will stutter but never actually halt.

I guess we'll just have to wait 'n' see, eh? Unless it's happened before, in which case we're seeing it again, but we don't know it.

My brain hurts.

DBPZ
Posts: 28
Joined: Mon Aug 31, 2009 5:17 am UTC

Re: 1266: "Halting Problem"

Postby DBPZ » Wed Sep 18, 2013 7:24 am UTC

A more sophisticated version

Code: Select all

from oracle import TheUniverseIsCollapsing

def DoesItHalt(program):
    while 1:
        while not TheUniverseIsCollapsing():
            pass
        yield 1


Much better now.






DBPZ wrote:

Code: Select all

from oracle import TheUniverseIsCollapsing

def DoesItHalt (program):
    while not TheUniverseIsCollapsing():
        pass
    return 1


User avatar
player_03
Posts: 19
Joined: Sat Oct 16, 2010 11:13 pm UTC

Re: 1266: "Halting Problem"

Postby player_03 » Wed Sep 18, 2013 7:32 am UTC

Call me weird, but I consider this the most depressing comic I've read in quite a while.

Afrael
Posts: 36
Joined: Mon Sep 20, 2010 10:23 am UTC

Re: 1266: "Halting Problem"

Postby Afrael » Wed Sep 18, 2013 7:42 am UTC

Hm. I interpreted it differently.

The way I see it, the fact that the parameter is called "program", not "program text" suggests that a program is passed to the function, which would presumably have already run (and halted). I thus interpret the method to be roughly equivalent to:

Code: Select all

define doesItHalt(program):
{
   eval(program);
   print(program + "halted!");
   return true;
}

Ronfar
Posts: 132
Joined: Mon Dec 04, 2006 6:04 am UTC

Re: 1266: "Halting Problem"

Postby Ronfar » Wed Sep 18, 2013 7:49 am UTC

I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone.


I do, but you'll need a microscope. Consider any single-celled organism that reproduces asexually. When a bacterium divides into two daughter cells, did the original cell die? It seems kind of strange to think so, but the original cell isn't there to be killed later, and it also doesn't make sense to think of the two daughter cells, along with their eventual descendants, as the same "thing" as the original parent cell.
- Doug

User avatar
TimXCampbell
Posts: 110
Joined: Wed Jul 27, 2011 4:26 am UTC
Location: Very Eastern Kentucky, USA
Contact:

Re: 1266: "Halting Problem"

Postby TimXCampbell » Wed Sep 18, 2013 7:56 am UTC

Ronfar wrote:It seems kind of strange to think so, but the original cell isn't there to be killed later, and it also doesn't make sense to think of the two daughter cells, along with their eventual descendants, as the same "thing" as the original parent cell.

It doesn't strike me as strange. You're not the same person now as you were when you wrote the text I've quoted above.

Nothing endures except change.

User avatar
da Doctah
Posts: 985
Joined: Fri Feb 03, 2012 6:27 am UTC

Re: 1266: "Halting Problem"

Postby da Doctah » Wed Sep 18, 2013 9:30 am UTC

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.

User avatar
da Doctah
Posts: 985
Joined: Fri Feb 03, 2012 6:27 am UTC

Re: 1266: "Halting Problem"

Postby da Doctah » Wed Sep 18, 2013 9:31 am UTC

TimXCampbell wrote:You're not the same person now as you were when you wrote the text I've quoted above..

The sentence I am now writing is the sentence you are now reading.

Contrary to expectations about such things, the two occurrences of "the sentence" have the same referent, but the two occurrences of "now" do not.

rjsteg
Posts: 18
Joined: Wed Dec 28, 2011 2:41 pm UTC

Re: 1266: "Halting Problem"

Postby rjsteg » Wed Sep 18, 2013 9:47 am UTC

In response to the alt text, I have two questions:

1) Is something *else* going on with Randall's personal life?
2) Has he possibly become spiritual?

Praying for NOT 1 AND 2,
Randy

Bastor
Posts: 12
Joined: Mon Mar 25, 2013 11:33 am UTC
Location: Bulgaria

Re: 1266: "Halting Problem"

Postby Bastor » Wed Sep 18, 2013 10:03 am UTC

da Doctah wrote:
TimXCampbell wrote:You're not the same person now as you were when you wrote the text I've quoted above..

The sentence I am now writing is the sentence you are now reading.

Contrary to expectations about such things, the two occurrences of "the sentence" have the same referent, but the two occurrences of "now" do not.

Actually three, since I also read it. xD
___________________________________________________
Anyway why does everyone go into "drama lama" mode over every single sadder comics.

It's going to halt sooner or later, since for it to actually finish both the author and every single person in the fan base needs to accept that it has come to its proper conclusion. Which will never happen.

So enjoy it while it lasts.

Amarantamin
Posts: 14
Joined: Mon Apr 01, 2013 9:27 am UTC

Re: 1266: "Halting Problem"

Postby Amarantamin » Wed Sep 18, 2013 10:24 am UTC

Bastor wrote:
da Doctah wrote:
TimXCampbell wrote:You're not the same person now as you were when you wrote the text I've quoted above..

The sentence I am now writing is the sentence you are now reading.

Contrary to expectations about such things, the two occurrences of "the sentence" have the same referent, but the two occurrences of "now" do not.

Actually three, since I also read it. xD


The original sentence contains both 'the sentence' and 'now' two times. The occurrences mentioned are not relative to the number of people who read the sentence.

jasper.a.visser
Posts: 4
Joined: Wed Sep 18, 2013 4:24 am UTC

Re: 1266: "Halting Problem"

Postby jasper.a.visser » Wed Sep 18, 2013 10:39 am UTC

Istaro wrote:Edit: Interesting. When I posted this, it was the second post, and it still was an hour or so later when I refreshed, but when I came back again many hours later, an intervening post had appeared.

It was my first post on this forum. Apparently first posts are moderated, and released for human consumption later. :)

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

Re: 1266: "Halting Problem"

Postby orthogon » Wed Sep 18, 2013 10:47 am UTC

jasper.a.visser wrote:
Istaro wrote:Edit: Interesting. When I posted this, it was the second post, and it still was an hour or so later when I refreshed, but when I came back again many hours later, an intervening post had appeared.

It was my first post on this forum. Apparently first posts are moderated, and released for human consumption later. :)

Nah. There are no humans on this forum. We're all AIs of various levels of sophistication (except for Klear, who's a p-zombie).
xtifr wrote:... and orthogon merely sounds undecided.

Prometheus
Posts: 28
Joined: Wed Mar 28, 2007 9:58 am UTC
Contact:

Re: 1266: "Halting Problem"

Postby Prometheus » Wed Sep 18, 2013 10:48 am UTC

That is the freakiest damn thing. The very last thing I did before checking xkcd this morning was read a short story (Oracle, by Greg Egan) where the halting problem was discussed.
Well I thought it was funny.

User avatar
Klear
Posts: 1965
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1266: "Halting Problem"

Postby Klear » Wed Sep 18, 2013 11:12 am UTC

orthogon wrote:Nah. There are no humans on this forum. We're all AIs of various levels of sophistication (except for Klear, who's a p-zombie).


Yeah, you keep telling yourself that. Oh wait, you can't.

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

Re: 1266: "Halting Problem"

Postby rmsgrey » Wed Sep 18, 2013 12:46 pm UTC

rjsteg wrote:In response to the alt text, I have two questions:

1) Is something *else* going on with Randall's personal life?
2) Has he possibly become spiritual?

Praying for NOT 1 AND 2,
Randy


My money's on the alt text just being an observation that it's impossible to prove that something is (strongly) immortal - the most you can show is that it hasn't died yet - and possibly that it has the potential to live indefinitely.

User avatar
cellocgw
Posts: 2055
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1266: "Halting Problem"

Postby cellocgw » Wed Sep 18, 2013 12:50 pm UTC

Cauchy wrote:I'm apparently not nerdy enterprizey enough to know what a "big picture solution" is.

FTFY :twisted:

Either that or he's referring to Click&Drag
https://app.box.com/witthoftresume
Former OTTer
Vote cellocgw for President 2020. #ScienceintheWhiteHouse http://cellocgw.wordpress.com
"The Planck length is 3.81779e-33 picas." -- keithl
" Earth weighs almost exactly π milliJupiters" -- what-if #146, note 7

User avatar
cellocgw
Posts: 2055
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1266: "Halting Problem"

Postby cellocgw » Wed Sep 18, 2013 12:53 pm UTC

Ronfar wrote:
I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone.


I do, but you'll need a microscope. Consider any single-celled organism that reproduces asexually. When a bacterium divides into two daughter cells, did the original cell die? It seems kind of strange to think so, but the original cell isn't there to be killed later, and it also doesn't make sense to think of the two daughter cells, along with their eventual descendants, as the same "thing" as the original parent cell.


Naaah.... pour a little bleach on them and they all die.

Also, in response to all those who posted

Code: Select all

while(true){program}
, I'd say it all depends on whether protons do or do not have infinite half-lives.

ETA: and let's not forget the infinite life of that special molecule Helium-Lanthanum (cross-scientific-fields bad joke)
https://app.box.com/witthoftresume
Former OTTer
Vote cellocgw for President 2020. #ScienceintheWhiteHouse http://cellocgw.wordpress.com
"The Planck length is 3.81779e-33 picas." -- keithl
" Earth weighs almost exactly π milliJupiters" -- what-if #146, note 7

User avatar
jc
Posts: 353
Joined: Fri May 04, 2007 5:48 pm UTC
Location: Waltham, Massachusetts, USA, Earth, Solar System, Milky Way Galaxy
Contact:

Re: 1266: "Halting Problem"

Postby jc » Wed Sep 18, 2013 1:24 pm UTC

Bastor wrote:
da Doctah wrote:
TimXCampbell wrote:You're not the same person now as you were when you wrote the text I've quoted above..

The sentence I am now writing is the sentence you are now reading.

Contrary to expectations about such things, the two occurrences of "the sentence" have the same referent, but the two occurrences of "now" do not.

Actually three, since I also read it. xD ...s.

Reminds me of a cute event years ago in an online discussion that had grown very confused and rancorous, with everyone talking past each other. Then someone posted "Does anyone know what time it is?" This was followed by many replies giving the current time, presumably from a handy clock. Eventually, people started posting comments observing that "people here can't even agree on such a simple question." There was a brief pause, until someone asked a different question ...
Last edited by jc on Wed Sep 18, 2013 7:20 pm UTC, edited 1 time in total.

User avatar
Tualha
Posts: 69
Joined: Wed Dec 12, 2007 12:18 pm UTC

Re: 1266: "Halting Problem"

Postby Tualha » Wed Sep 18, 2013 1:32 pm UTC

Ah, but what if you're in Greg Egan's "Dust" universe in Permutation City? Then you're back to theory :)

User avatar
Tualha
Posts: 69
Joined: Wed Dec 12, 2007 12:18 pm UTC

Re: 1266: "Halting Problem"

Postby Tualha » Wed Sep 18, 2013 1:33 pm UTC

rjsteg wrote:In response to the alt text, I have two questions:

1) Is something *else* going on with Randall's personal life?
2) Has he possibly become spiritual?

Praying for NOT 1 AND 2,
Randy

Fervently hoping for (NOT 1) AND (NOT 2).

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

Re: 1266: "Halting Problem"

Postby Kit. » Wed Sep 18, 2013 1:55 pm UTC

Sorry, Randall, but the comic reminded me of the two following quotes:

Spoiler:
Beware of bugs in the above code; I have only proved it correct, not tried it.

and
Spoiler:
...there is always a well-known solution to every human problem — neat, plausible, and wrong.

xtifr
Posts: 365
Joined: Wed Oct 01, 2008 6:38 pm UTC

Re: 1266: "Halting Problem"

Postby xtifr » Wed Sep 18, 2013 8:54 pm UTC

I'd say the biggest flaw in today's comic is that it assumes we can't eventually build a computer that will be able to bootstrap itself into new universes (possibly creating them as necessary) to continue its computation.

The heat death of this universe isn't necessarily a limiting factor to computation. :mrgreen:
"[T]he author has followed the usual practice of contemporary books on graph theory, namely to use words that are similar but not identical to the terms used in other books on graph theory."
-- Donald Knuth, The Art of Computer Programming, Vol I, 3rd ed.

User avatar
bmonk
Posts: 662
Joined: Thu Feb 18, 2010 10:14 pm UTC
Location: Schitzoed in the OTT between the 2100s and the late 900s. Hoping for singularity.

Re: 1266: "Halting Problem"

Postby bmonk » Wed Sep 18, 2013 9:18 pm UTC

xtifr wrote:I'd say the biggest flaw in today's comic is that it assumes we can't eventually build a computer that will be able to bootstrap itself into new universes (possibly creating them as necessary) to continue its computation.

The heat death of this universe isn't necessarily a limiting factor to computation. :mrgreen:

I thought of Asimov's "The Last Question."
Having become a Wizard on n.p. 2183, the Yellow Piggy retroactively appointed his honorable self a Temporal Wizardly Piggy on n.p.1488, not to be effective until n.p. 2183, thereby avoiding a partial temporal paradox. Since he couldn't afford two philosophical PhDs to rule on the title.

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

Re: 1266: "Halting Problem"

Postby Pfhorrest » Wed Sep 18, 2013 9:23 pm UTC

Tangential to this, but the titular Last Question makes me wonder: has anyone here seen or heard of a sci-fi story exploring the implications of a simple device which does nothing but reverse entropy? Say, a "fair refrigerator", one that generates power instead of using it, by extracting the heat from its contents. Or any kind of gizmo which sucks up ambient heat and produces useful energy. Divorced from some kind of far-future science-fiction background with all kinds of other changes, just an exploration of what if such a thing were invented and introduced into the contemporary world?

Actually, that might make a good what-if question for Randall...
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. » Wed Sep 18, 2013 9:58 pm UTC

xtifr wrote:I'd say the biggest flaw in today's comic is that it assumes

I'd say the biggest flaw in this comic is that it makes this possible.

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

Re: 1266: "Halting Problem"

Postby Pfhorrest » Wed Sep 18, 2013 11:27 pm UTC

How does the Halting Problem entail the Principle of Explosion? Undecidable questions don't cause explosion, contradictions do. Even if undecidable questions somehow necessarily had answers that were not "yes" or "no" (violating the law of the excluded middle), that would not imply that they had answers which were both "yes" and "no" (violating the law of non-contradiction), and the latter is what causes explosion.
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)

Arky
Posts: 183
Joined: Wed May 26, 2010 7:23 am UTC

Re: 1266: "Halting Problem"

Postby Arky » Thu Sep 19, 2013 12:13 am UTC

Antior wrote:For those who aren't as nerdy as some of you, here's the Wikipedia definition of the Halting Problem:

Wikipedia wrote:In computability theory, the halting problem can be stated as follows: "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever". This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, what became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.


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"?
Veteran of the One True Thread. And now the Too True Thread?

jasper.a.visser
Posts: 4
Joined: Wed Sep 18, 2013 4:24 am UTC

Re: 1266: "Halting Problem"

Postby jasper.a.visser » Thu Sep 19, 2013 12:20 am UTC

Pfhorrest wrote:Tangential to this, but the titular Last Question makes me wonder: has anyone here seen or heard of a sci-fi story exploring the implications of a simple device which does nothing but reverse entropy? Say, a "fair refrigerator", one that generates power instead of using it, by extracting the heat from its contents. Or any kind of gizmo which sucks up ambient heat and produces useful energy. Divorced from some kind of far-future science-fiction background with all kinds of other changes, just an exploration of what if such a thing were invented and introduced into the contemporary world?

Actually, that might make a good what-if question for Randall...

Actually, there's a bit in the most recent Futurama episode (7x26) that would qualify for that (the scene with the diamonds). Or pretty much any time travel fiction fits the bill, although the main characters never seem to realize the implications of their device on the 2nd law of thermodynamics.

Hope someone gives you a better answer though; it would be an interesting read. :)


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 48 guests