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"

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"

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"

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.

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

Re: 1266: "Halting Problem"

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"

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"

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"

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.

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

Re: 1266: "Halting Problem"

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.

keithl
Posts: 662
Joined: Mon Aug 01, 2011 3:46 pm UTC

Re: 1266: "Halting Problem"

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"

Code: Select all

`from oracle import TheUniverseIsCollapsingdef DoesItHalt (program):    while not TheUniverseIsCollapsing():        pass    return 1`

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

Re: 1266: "Halting Problem"

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?

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

Re: 1266: "Halting Problem"

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"

A more sophisticated version

Code: Select all

`from oracle import TheUniverseIsCollapsingdef DoesItHalt(program):    while 1:        while not TheUniverseIsCollapsing():            pass        yield 1`

Much better now.

DBPZ wrote:

Code: Select all

`from oracle import TheUniverseIsCollapsingdef DoesItHalt (program):    while not TheUniverseIsCollapsing():        pass    return 1`

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

Re: 1266: "Halting Problem"

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"

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"

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

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

Re: 1266: "Halting Problem"

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.

da Doctah
Posts: 997
Joined: Fri Feb 03, 2012 6:27 am UTC

Re: 1266: "Halting Problem"

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.

da Doctah
Posts: 997
Joined: Fri Feb 03, 2012 6:27 am UTC

Re: 1266: "Halting Problem"

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"

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"

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"

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"

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.

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

Re: 1266: "Halting Problem"

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"

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.

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

Re: 1266: "Halting Problem"

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: 3656
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1266: "Halting Problem"

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.

cellocgw
Posts: 2068
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1266: "Halting Problem"

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

FTFY

Either that or he's referring to Click&Drag
resume
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

cellocgw
Posts: 2068
Joined: Sat Jun 21, 2008 7:40 pm UTC

Re: 1266: "Halting Problem"

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

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

Re: 1266: "Halting Problem"

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.

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

Re: 1266: "Halting Problem"

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

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

Re: 1266: "Halting Problem"

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"

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: 366
Joined: Wed Oct 01, 2008 6:38 pm UTC

Re: 1266: "Halting Problem"

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.
"[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.

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"

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.

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.

Pfhorrest
Posts: 5487
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 1266: "Halting Problem"

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"

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.

Pfhorrest
Posts: 5487
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 1266: "Halting Problem"

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"

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"

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: Google Feedfetcher and 110 guests