back

by shagie·8y ago·view on hn ↗
Interesting slides, though the end with the simulation goes a bit... odd. I suspect some context or overriding narration is lost in going from dominoes to the simulation hypothesis.

I also believe that the Wang tile set is misplaced in the "accidentally Turing complete". That was part of his conjecture. From Wikipedia https://en.wikipedia.org/wiki/Hao_Wang_(academic)

> One of Wang's most important contributions was the Wang tile. He showed that any Turing machine can be turned into a set of Wang tiles. The first noted example of aperiodic tiling is a set of Wang tiles, whose nonexistence Wang had once conjectured, discovered by his student Robert Berger in 1966.

He was able to transform the TM into tiles - that was their purpose. Their importance is in the relation in reducing the periodic tiling to solving the halting problem.

From https://www.cs.duke.edu/courses/fall08/cps234/projects/tilin...

> Previous to Berger’s result, Wang himself showed a restricted version of the tiling problem, where only a certain tile was allowed at the origin, to be undecidable by reducing the halting problem to it. This and later work in tilings gave a method for simulating Turing machines using tiles, paving the way for thinking of tiles as a model of Turing universal computation.

Also fun reading on Wang tiles - http://math.oregonstate.edu/~math_reu/proceedings/REU_Procee... which shows some of the programs written in wang tile sets (palindrome validation fibonacci sequence, and addition of two numbers). A better view of those programs can be seen at https://grahamshawcross.com/2012/10/12/wang-tiles-and-turing... (consider your next bathroom remodel project)

1 comments
I think his point at the end was that computation is substrate-independent; i.e. there is nothing special or magical about silicon and electricity. In a sense, the universe itself can be said to be acting like a computer.
Long ago (I'm thinking early 80s) in Scientific American, I recall a story about the implementation of a computer(?) in a giant train switching yard. That one, I can't find. Though the story of Apraphul ( http://robert.surton.net/cs160/apraphulian.pdf ) also points to the "nothing magical about silicon and electricity".

There are lots of ways to do computation. DNA for example. http://www.nature.com/news/2000/000113/full/news000113-10.ht...

Its just that going from the accidentally Turing complete and physical implementations of logic gates to the simulation hypothesis was a sudden shift in the narrative I was making for myself while reading the slides.

The Sci Am article was a Computer Recreations column, probably by A.K. Dewdney.
After some digging, it is "Mathematical Recreations: A Subway Named Turing", Scientific American (September): 104,106-107 by Ian Steward which can be read at http://dev.whydomath.org/Reading_Room_Material/ian_stewart/C... (the key memory points that confirms it is the conversational mode and the passage "And I swear there's a sign just along the tunnel that reads 'flip-flop 7743A/91.'"

Though A.K. Dewdney did write on a similar topic - Dewdney, A. K. 1987. Algopuzzles: wherein trains of thought follow algorithmic tracks to solutions. Scientific American 256(6):128–130.

and http://bit-player.org/wp-content/extras/bph-publications/AmS... is a some other interesting puzzles on the subject.