explain xkcd - User contributions [en]

1266: Halting Problem

2013-09-18T09:28:43Z

74.125.57.36: /* Explanation */ Fix Wikipedia link

{{comic
| number = 1266
| date = September 18, 2013
| title = Halting Problem
| image = halting_problem.png
| titletext = I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone.
}}

==Explanation==
{{incomplete}}
In 1936 {{w|Alan Turing}} proved that it's not possible to decide whether an arbitrary program will eventually halt, or run forever. This was later called the {{w|Halting problem}} by {{w|Martin Davis}}. The official definition of the problem is to write a program (actually, a {{w|Turing Machine}}) that accepts as parameters a program and its parameters. That program needs to decide, in finite time, whether that program will ever halt running these parameters.

The halting problem is a cornerstone problem in computer science. It is used mainly as a way to prove a given task is impossible, by showing that solving that task will allow one to solve the halting problem.

[[Randall]], however, is providing a simpler solution. He implements his own code for the question ''"Does it halt?"'' which always returns a positive answer, directing us to look at the bigger picture.

For all '''practical''' purposes, this is the correct solution. Given enough time, any program will halt. This is due to factors external to the actual program. Sooner or later, electricity will give out, or the memory containing the program will get corrupted by cosmic rays, or corrosion will eat away the silicon in the CPU. Nothing lasts forever, and this includes a running program.

From the '''theoretical''' point of view, this is not true: Turing machine will never have a hardware failure because it's not real machine, it's theoretical construct, and it's '''defined''' to not have any. Similarly, 1/3 + 1/3 + 1/3 = 1 no matter what any real hardware you are computing it on claims.

The title text further relates to this issue by claiming to have found a case where something need not die, but Randall does not know how to actually show it to anyone, because just the fact everyone will die sooner that this thing it doesn't prove it will not die. The wording of the title text might also be a reference to {{w|Fermat's Last Theorem}}.

It should be noted that Randall's solution does not, in fact, solve the halting problem. The halting problem requires two parameters (a program and its parameters), while Randall's function only accepts one. His solution does not match the interface required by the problem.

==Transcript==
'''Define''' DoesItHalt(program):
{
'''return''' true;
}
:The big picture solution to the halting problem.

{{comic discussion}}
[[Category:Computers‏‎]]

1266: Halting Problem

2013-09-18T09:27:52Z

74.125.57.36: /* Explanation */ Wording of title text sounds like Fermat's Last Theorem, so mention that.

{{comic
| number = 1266
| date = September 18, 2013
| title = Halting Problem
| image = halting_problem.png
| titletext = I found a counterexample to the claim that all things must someday die, but I don't know how to show it to anyone.
}}

==Explanation==
{{incomplete}}
In 1936 {{w|Alan Turing}} proved that it's not possible to decide whether an arbitrary program will eventually halt, or run forever. This was later called the {{w|Halting problem}} by {{w|Martin Davis}}. The official definition of the problem is to write a program (actually, a {{w|Turing Machine}}) that accepts as parameters a program and its parameters. That program needs to decide, in finite time, whether that program will ever halt running these parameters.

The halting problem is a cornerstone problem in computer science. It is used mainly as a way to prove a given task is impossible, by showing that solving that task will allow one to solve the halting problem.

[[Randall]], however, is providing a simpler solution. He implements his own code for the question ''"Does it halt?"'' which always returns a positive answer, directing us to look at the bigger picture.

For all '''practical''' purposes, this is the correct solution. Given enough time, any program will halt. This is due to factors external to the actual program. Sooner or later, electricity will give out, or the memory containing the program will get corrupted by cosmic rays, or corrosion will eat away the silicon in the CPU. Nothing lasts forever, and this includes a running program.

From the '''theoretical''' point of view, this is not true: Turing machine will never have a hardware failure because it's not real machine, it's theoretical construct, and it's '''defined''' to not have any. Similarly, 1/3 + 1/3 + 1/3 = 1 no matter what any real hardware you are computing it on claims.

The title text further relates to this issue by claiming to have found a case where something need not die, but Randall does not know how to actually show it to anyone, because just the fact everyone will die sooner that this thing it doesn't prove it will not die. The wording of the title text might also be a reference to {w|Fermat's Last Theorem}.

It should be noted that Randall's solution does not, in fact, solve the halting problem. The halting problem requires two parameters (a program and its parameters), while Randall's function only accepts one. His solution does not match the interface required by the problem.

==Transcript==
'''Define''' DoesItHalt(program):
{
'''return''' true;
}
:The big picture solution to the halting problem.

{{comic discussion}}
[[Category:Computers‏‎]]

1249: Meteor Showers

2013-08-09T15:31:20Z

74.125.57.36: Add note about leonids

{{comic
| number = 1249
| date = August 9, 2013
| title = Meteor Showers
| image = meteor showers.png
| titletext = Remember, meteors always hit the tallest object around.
}}

This comic spoofs the way that astronomical events are often reported in the mass media — events are often tagged with undeserved superlatives or described as being more dramatic than they actually are. In some cases, outright misinformation is spread. This phenomenon occurs in part the result of over-eager scientists, and in part because of journalists misunderstanding the subject.

Meteor showers, for example, typically occur regularly each year. Sometimes meteor showers are in fact likely to be relatively spectacular - for example when the peak of the shower occurs when your part of the world is in darkness and there is little moonlight. However, even in these cases it must be understood that there is nothing unusual about the meteor shower itself.

Most of the meteor showers listed in the comic are real. These are the {{w|Quadrantids}}, [http://meteorshowersonline.com/showers/alpha-beta_centaurids.html Centaurids], {{w|Lyrids}}, Daytime Zeta Perseids, {{w|June Bootids|June Boötids}}, {{w|Southern Delta Aquariids}}, {{w|Perseids}}, {{w|Draconids}}, {{w|Orionids}}, {{w|Leonids}}, and {{w|Geminids}}.

Some of the showers are made up (see below).

*Quadrantids - January 4th - Bring pets inside during peak activity
*Tricuspids - January 21st - Not viewable in region 2 countries
:Made up. Apparently a play on the {{w|tricuspid valve}} in mammalian hearts. The mention of "Region 2" is a reference to {{w|region locking}}, a DRM scheme intended to limit media to certain areas. DRM of course does not apply to natural events. But ironically, meteor showers are also geographically restricted, and the visible area might roughly coincide with a DRM region. Further irony is that "Region 2" is actually Europe, Middle East, Egypt, Japan, South Africa, Swaziland, Lesotho, Greenland, French Overseas departments and territories, meaning that it's not strictly geographical, much is the mess that is DRM.
*Centaurids - February 6th - Too faint to see without going outside
:Since most houses have opaque roofs, it would take a ''very'' bright meteor to be visible without going outside.
*Beta Aquariids - February 10th - Inverted shower converges toward Aquarius instead of radiating away
*Chelyabids - February 15th - Only one meteor per shower, but it's big.
:Made up. A reference to the February 15, 2013, {{w|Chelyabinsk meteor}} whose explosion shattered windows within a large radius.
*Lyrids - April 22nd - Meteors sometimes scream
*Daytime Zeta Perseids - June 9th - Likely a NASA hoax
*June Boötids - June 27th - 50/50 mix of meteors and shooting stars
:The "50/50 mix of meteors and shooting stars" is a joke, as "meteor" and "shooting star" are synonymous.
*Southern Delta Aquariids - July 19th - Meteors very bright, but stationary
*Dromaeosaurids - July 22th - Fast, highly intelligent, can open doors
:Made up. Dromaeosaurids are dinosaurs belonging to {{w|Dromaeosauridae}}, the family containing the genus ''Velociraptor'', well-known from the movie Jurassic Park, and a [[:Category:Velociraptors|popular xkcd-theme]]. When the comic was originally published, the date listed for this shower was June 12th. The main events of Jurassic Park take place on June 11th and 12th.
*Perseids - August 12th - Instead of falling from sky, meteors erupt from ground
*Tau Pyramids - August 15th - Visible even when eyes are closed
:Probably a reference to pyramidal cells, a type of neuron in the brain that is linked to cognition.
*Draconids - October 8th - Very slow, but follow you if you run
*Orionids - October 21st - Entire shower happens at once
*Leonids - November 17th - In 1966, unusually active Leonid shower killed God
:There ''was'' a very active Leonid shower. However, it occurred several months after the article "Is God Dead?" published in ''Time Magazine'' that year.
*Geminids - December 13th - Can be deflected with tennis rackets

The title text refers to the folk wisdom that ''lightning'' strikes the tallest thing around. [[Randall]] expressed frustration over how "maddeningly inexact" that statement is, and elaborated on the problem mathematically, on his [[what if?]]-blog, in the [http://what-if.xkcd.com/16/ post on lightning].

==Transcript==
:The xkcd guide to meteor showers
[There is a three-column table]
:; Name - Peak - Notes
:Quadrantids - January 4th - Bring pets inside during peak activity
:Tricuspids - January 21st - Not viewable in region 2 countries
:Centaurids - February 6th - Too faint to see without going outside
:Beta Aquariids - February 10th - Inverted shower converges toward Aquarius instead of radiating away
:Chelyabids - February 15th - Only one meteor per shower, but it's big.
:Lyrids - April 22nd - Meteors sometimes scream
:Daytime Zeta Perseids - June 9th - Likely a NASA hoax
:June Boötids - June 27th - 50/50 mix of meteors and shooting stars
:Southern Delta Aquariids - July 19th - Meteors very bright, but stationary
:Dromaeosaurids - July 22th - Fast, highly intelligent, can open doors
:Perseids - August 12th - Instead of falling from sky, meteors erupt from ground
:Tau Pyramids - August 15th - Visible even when eyes are closed
:Draconids - October 8th - Very slow, but follow you if you run
:Orionids - October 21st - Entire shower happens at once
:Leonids - November 17th - In 1966, unusually active Leonid shower killed God
:Geminids - December 13th - Can be deflected with tennis rackets

{{comic discussion}}
[[Category:Charts]]

Talk:1249: Meteor Showers

2013-08-09T15:08:00Z

74.125.57.36: Lyrids question

The dates are not in order {{unsigned ip|‎99.108.140.97}}

Maybe the tennis reference is to Bob and Mike Bryan, they are twins. [[Special:Contributions/83.227.33.35|83.227.33.35]] 09:36, 9 August 2013 (UTC)

The date for Dromaeosaurids was originally June 12, but on the page displayed at 9:44 ET, is now July 22.

Lyrids: Scream because of the similarity to "Lyrics"? [[Special:Contributions/74.125.57.36|74.125.57.36]] 15:08, 9 August 2013 (UTC)

1249: Meteor Showers

2013-08-09T15:06:17Z

74.125.57.36: Add note about Beta Aquariids

{{comic
| number = 1249
| date = August 9, 2013
| title = Meteor Showers
| image = meteor showers.png
| titletext = Remember, meteors always hit the tallest object around.
}}

This comic spoofs the way that astronomical events are often reported in the mass media — events are often tagged with undeserved superlatives or described as being more dramatic than they actually are. In some cases, outright misinformation is spread. This phenomenon occurs in part the result of over-eager scientists, and in part because of journalists misunderstanding the subject.

Meteor showers, for example, typically occur regularly each year. Sometimes meteor showers are in fact likely to be relatively spectacular - for example when the peak of the shower occurs when your part of the world is in darkness and there is little moonlight. However, even in these cases it must be understood that there is nothing unusual about the meteor shower itself.

Most of the meteor showers listed in the comic are real. These are the {{w|Quadrantids}}, [http://meteorshowersonline.com/showers/alpha-beta_centaurids.html Centaurids], {{w|Lyrids}}, Daytime Zeta Perseids, {{w|June Bootids|June Boötids}}, {{w|Southern Delta Aquariids}}, {{w|Perseids}}, {{w|Draconids}}, {{w|Orionids}}, {{w|Leonids}}, and {{w|Geminids}}.

Some of the showers are made up (see below).

*Quadrantids - January 4th - Bring pets inside during peak activity
*Tricuspids - January 21st - Not viewable in region 2 countries
:Made up. Apparently a play on the {{w|tricuspid valve}} in mammalian hearts. The mention of "Region 2" is a reference to {{w|region locking}}, a DRM scheme intended to limit media to certain areas. DRM of course does not apply to natural events. But ironically, meteor showers are also geographically restricted, and the visible area might roughly coincide with a DRM region. Further irony is that "Region 2" is actually Europe, Middle East, Egypt, Japan, South Africa, Swaziland, Lesotho, Greenland, French Overseas departments and territories, meaning that it's not strictly geographical, much is the mess that is DRM.
*Centaurids - February 6th - Too faint to see without going outside
:Since most houses have opaque roofs, it would take a ''very'' bright meteor to be visible without going outside.
*Beta Aquariids - February 10th - Inverted shower converges toward Aquarius instead of radiating away
*Chelyabids - February 15th - Only one meteor per shower, but it's big.
:Made up. A reference to the February 15, 2013, {{w|Chelyabinsk meteor}} whose explosion shattered windows within a large radius.
*Lyrids - April 22nd - Meteors sometimes scream
*Daytime Zeta Perseids - June 9th - Likely a NASA hoax
*June Boötids - June 27th - 50/50 mix of meteors and shooting stars
:The "50/50 mix of meteors and shooting stars" is a joke, as "meteor" and "shooting star" are synonymous.
*Southern Delta Aquariids - July 19th - Meteors very bright, but stationary
*Dromaeosaurids - July 22th - Fast, highly intelligent, can open doors
:Made up. Dromaeosaurids are dinosaurs belonging to {{w|Dromaeosauridae}}, the family containing the genus ''Velociraptor'', well-known from the movie Jurassic Park, and a [[:Category:Velociraptors|popular xkcd-theme]]. When the comic was originally published, the date listed for this shower was June 12th. The main events of Jurassic Park take place on June 11th and 12th.
*Perseids - August 12th - Instead of falling from sky, meteors erupt from ground
*Tau Pyramids - August 15th - Visible even when eyes are closed
:Probably a reference to pyramidal cells, a type of neuron in the brain that is linked to cognition.
*Draconids - October 8th - Very slow, but follow you if you run
*Orionids - October 21st - Entire shower happens at once
*Leonids - November 17th - In 1966, unusually active Leonid shower killed God
*Geminids - December 13th - Can be deflected with tennis rackets

The title text refers to the folk wisdom that ''lightning'' strikes the tallest thing around. [[Randall]] expressed frustration over how "maddeningly inexact" that statement is, and elaborated on the problem mathematically, on his [[what if?]]-blog, in the [http://what-if.xkcd.com/16/ post on lightning].

==Transcript==
:The xkcd guide to meteor showers
[There is a three-column table]
:; Name - Peak - Notes
:Quadrantids - January 4th - Bring pets inside during peak activity
:Tricuspids - January 21st - Not viewable in region 2 countries
:Centaurids - February 6th - Too faint to see without going outside
:Beta Aquariids - February 10th - Inverted shower converges toward Aquarius instead of radiating away
:Chelyabids - February 15th - Only one meteor per shower, but it's big.
:Lyrids - April 22nd - Meteors sometimes scream
:Daytime Zeta Perseids - June 9th - Likely a NASA hoax
:June Boötids - June 27th - 50/50 mix of meteors and shooting stars
:Southern Delta Aquariids - July 19th - Meteors very bright, but stationary
:Dromaeosaurids - July 22th - Fast, highly intelligent, can open doors
:Perseids - August 12th - Instead of falling from sky, meteors erupt from ground
:Tau Pyramids - August 15th - Visible even when eyes are closed
:Draconids - October 8th - Very slow, but follow you if you run
:Orionids - October 21st - Entire shower happens at once
:Leonids - November 17th - In 1966, unusually active Leonid shower killed God
:Geminids - December 13th - Can be deflected with tennis rackets

{{comic discussion}}
[[Category:Charts]]

1249: Meteor Showers

2013-08-09T15:02:37Z

74.125.57.36: Original date of Dromaeosaurids (according to the comments) is significant to the film.

{{comic
| number = 1249
| date = August 9, 2013
| title = Meteor Showers
| image = meteor showers.png
| titletext = Remember, meteors always hit the tallest object around.
}}

This comic spoofs the way that astronomical events are often reported in the mass media — events are often tagged with undeserved superlatives or described as being more dramatic than they actually are. In some cases, outright misinformation is spread. This phenomenon occurs in part the result of over-eager scientists, and in part because of journalists misunderstanding the subject.

Meteor showers, for example, typically occur regularly each year. Sometimes meteor showers are in fact likely to be relatively spectacular - for example when the peak of the shower occurs when your part of the world is in darkness and there is little moonlight. However, even in these cases it must be understood that there is nothing unusual about the meteor shower itself.

Most of the meteor showers listed in the comic are real. These are the {{w|Quadrantids}}, [http://meteorshowersonline.com/showers/alpha-beta_centaurids.html Centaurids], {{w|Lyrids}}, Daytime Zeta Perseids, {{w|June Bootids|June Boötids}}, {{w|Southern Delta Aquariids}}, {{w|Perseids}}, {{w|Draconids}}, {{w|Orionids}}, {{w|Leonids}}, and {{w|Geminids}}.

Some of the showers are made up (see below).

*Quadrantids - January 4th - Bring pets inside during peak activity
*Tricuspids - January 21st - Not viewable in region 2 countries
:Made up. Apparently a play on the {{w|tricuspid valve}} in mammalian hearts. The mention of "Region 2" is a reference to {{w|region locking}}, a DRM scheme intended to limit media to certain areas. DRM of course does not apply to natural events. But ironically, meteor showers are also geographically restricted, and the visible area might roughly coincide with a DRM region. Further irony is that "Region 2" is actually Europe, Middle East, Egypt, Japan, South Africa, Swaziland, Lesotho, Greenland, French Overseas departments and territories, meaning that it's not strictly geographical, much is the mess that is DRM.
*Centaurids - February 6th - Too faint to see without going outside
*Beta Aquariids - February 10th - Inverted shower converges toward Aquarius instead of radiating away
*Chelyabids - February 15th - Only one meteor per shower, but it's big.
:Made up. A reference to the February 15, 2013, {{w|Chelyabinsk meteor}} whose explosion shattered windows within a large radius.
*Lyrids - April 22nd - Meteors sometimes scream
*Daytime Zeta Perseids - June 9th - Likely a NASA hoax
*June Boötids - June 27th - 50/50 mix of meteors and shooting stars
:The "50/50 mix of meteors and shooting stars" is a joke, as "meteor" and "shooting star" are synonymous.
*Southern Delta Aquariids - July 19th - Meteors very bright, but stationary
*Dromaeosaurids - July 22th - Fast, highly intelligent, can open doors
:Made up. Dromaeosaurids are dinosaurs belonging to {{w|Dromaeosauridae}}, the family containing the genus ''Velociraptor'', well-known from the movie Jurassic Park, and a [[:Category:Velociraptors|popular xkcd-theme]]. When the comic was originally published, the date listed for this shower was June 12th. The main events of Jurassic Park take place on June 11th and 12th.
*Perseids - August 12th - Instead of falling from sky, meteors erupt from ground
*Tau Pyramids - August 15th - Visible even when eyes are closed
:Probably a reference to pyramidal cells, a type of neuron in the brain that is linked to cognition.
*Draconids - October 8th - Very slow, but follow you if you run
*Orionids - October 21st - Entire shower happens at once
*Leonids - November 17th - In 1966, unusually active Leonid shower killed God
*Geminids - December 13th - Can be deflected with tennis rackets

The title text refers to the folk wisdom that ''lightning'' strikes the tallest thing around. [[Randall]] expressed frustration over how "maddeningly inexact" that statement is, and elaborated on the problem mathematically, on his [[what if?]]-blog, in the [http://what-if.xkcd.com/16/ post on lightning].

==Transcript==
:The xkcd guide to meteor showers
[There is a three-column table]
:; Name - Peak - Notes
:Quadrantids - January 4th - Bring pets inside during peak activity
:Tricuspids - January 21st - Not viewable in region 2 countries
:Centaurids - February 6th - Too faint to see without going outside
:Beta Aquariids - February 10th - Inverted shower converges toward Aquarius instead of radiating away
:Chelyabids - February 15th - Only one meteor per shower, but it's big.
:Lyrids - April 22nd - Meteors sometimes scream
:Daytime Zeta Perseids - June 9th - Likely a NASA hoax
:June Boötids - June 27th - 50/50 mix of meteors and shooting stars
:Southern Delta Aquariids - July 19th - Meteors very bright, but stationary
:Dromaeosaurids - July 22th - Fast, highly intelligent, can open doors
:Perseids - August 12th - Instead of falling from sky, meteors erupt from ground
:Tau Pyramids - August 15th - Visible even when eyes are closed
:Draconids - October 8th - Very slow, but follow you if you run
:Orionids - October 21st - Entire shower happens at once
:Leonids - November 17th - In 1966, unusually active Leonid shower killed God
:Geminids - December 13th - Can be deflected with tennis rackets

{{comic discussion}}
[[Category:Charts]]