205: Candy Button Paper

Explain xkcd: It's 'cause you're dumb.
Revision as of 08:05, 13 April 2018 by Herobrine (talk | contribs) (Explanation)
Jump to: navigation, search
Candy Button Paper
Nonrewriteable tape?
Title text: Nonrewriteable tape?

Explanation

This comic refers to Candy Buttons, a type of candy sold by Necco in the U.S. since 1980. Because they were glued to paper, each candy button would have some paper stuck to it. As said in the comic, some kids would carefully check each candy button to make sure they would accidentally eat paper, while some kids didn't care and ripped them off, eating large scraps of paper in the process.

Because of the resemblance of the strips of paper to the tape of a Turing Machine, a small minority of children (possibly only Randall or some of his friends) pretended to be a Turing Machine by creating rules and executing them upon the tape of candy exactly like a real Turing Machine would do.

The title text refers to the fact that, although it would be hypothetically possible to create a Turing Machine that can only delete symbols, the information density of the tape would be greatly reduced, and the original Turing Machine could read and write from the tape it operated on.

Transcript

When it came to eating strips of candy buttons, there were two main strategies. Some kids carefully removed each bead, checking closely for paper residue before eating.
[To the right, a small section of a strip of Candy Buttons paper is shown. 2 red buttons have been removed from the top of the strip.]
[To the left, a long strip is shown. It seems to be waving in the air.]
Others tore the candy off haphazardly, swallowing large scraps of paper as they ate.
Then there were the lonely few of us who moved back and forth on the strip, eating rows of beads here and there, pretending we were Turing machines.
[A strip is shown from bird's eye view. Many rows of buttons have already been eaten.]


comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!

Discussion

It is possible to run a Turing machine on a candy belt:

Marvin Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J. In particular see p. 262ff (italics in original): "We can now demonstrate the remarkable fact, first shown by Wang [1957], that for any Turing machine T there is an equivalent Turing machine TN that never changes a once-written symbol! In fact, we will construct a two-symbol machine TN that can only change blank squares on its tape to 1's but can not change a 1 back to a blank." Minsky then offers a proof of this. -- Kopa Leo 69.163.36.90 16:01, 6 July 2013 (UTC)

In my opinion, intuitively, when writing is demanded, a turing machine just have to copy those symbols to a new location, minding the symbol that needs to be written. It can have a start-of-data mark so this would be transparent to other operations 173.245.48.96 05:45, 27 July 2014 (UTC)

so I'm the only one that put them in a loop, then moved it one button down on one side? 108.162.245.151 (talk) (please sign your comments with ~~~~)

Candy button paper was around long before 1980. I remember it from the 1950s. 108.162.241.123 17:59, 2 October 2016 (UTC)

If candy buttons were two-sided, I would make it into a Möbius strip. 625571b7-aa66-4f98-ac5c-92464cfb4ed8 (talk) 14:28, 14 March 2017 (UTC)

Doesn't Randall mention three different strategies? The comic says two, however.

There are two main strategies (careful and fast) and one very uncommon strategy (Turing). 162.158.186.60 21:14, 3 August 2017 (UTC)

There's a proof from Sipser's Introduction to the Theory of Computation (2nd ed), [exercise 3.10: https://archive.org/stream/IntroductionToTheoryOfComputation/introduction%20to%20theory%20of%20computation_djvu.txt]:

We first simulate an ordinary Turing machine by a write-twice Turing machine. The write-twice machine simulates a single step of the original machine by copying the entire tape over to a fresh portion of the tape to the right-hand side of the currently used portion. The copying procedure operates character by character, marking a character as it is copied. This procedure alters each tape square twice, once to write the character for the first time and again to mark that it has been copied. The position of the original Turing machine’s tape head is marked on the tape. When copying the cells at, or adjacent to, the marked position, the tape contents is updated according to the rules of the original Turing machine.

To carry out the simulation with a write-once machine, operate as before, except that each cell of the previous tape is now represented by two cells. The first of these contains the original machine’s tape symbol and the second is for the mark used in the copying procedure. The input is not presented to the machine in the format with two cells per symbol, so the very first time the tape is copied, the copying marks are put directly over the input symbols. -- Kopa Leo 108.162.250.41 12:03, 17 November 2018 (UTC)

Note: Alan Kay recommended Computation: Finite and Infinite Machines as a classic. -- Kopa Leo 172.70.206.151 08:38, 26 December 2021 (UTC)

i was a weird mix between the 3 back in my day when eating similar candies: which one depended on the day An user who has no account yet (talk) 14:15, 6 September 2023 (UTC)