Hacker News new | comments | show | ask | jobs | submit login
From Brainfuck to Domino Computers [pdf] (seriot.ch)
29 points by mpweiher 11 months ago | hide | past | web | favorite | 10 comments

On the topic of esoteric coding, I highly recommend Daniel Temkin's esoteric.codes[0]. It has interviews with esolang creators, essays and more. While you're there, read his short essay "The Less Humble Programmer"[1]. I'm sure it will ring true for many of us:

> Practices like esolangs, obfuscated code, one-liners, and code golf are all Less Humble practices. They create spaces for play in code, where it’s okay to use weird hacks, write the unreadable, or stretch the boundaries of programming.

> Wendy Hui Kyong Chun has written about how giving up the direct interface with the machine was hard for early programmers. Chun quotes John Backus, developer of FORTRAN about the “black art” of early coding, saying they had a:

> “chauvinistic pride in their frontiersmanship and a corresponding conservatism, so many programmers of the 1950s began to regard themselves as members of a priesthood guarding skills and mysteries far too complex for ordinary mortals. Languages like FORTRAN opened up this world to people who were not trained in this black art.”

> In a sense, alternative coding practices recreate this sense of code as an esoteric knowledge. Here not in a chauvansitic way, but with a sense of excitement in breaking new ground within deliberately obscure rules offered by an esolang or a set of code golf constraints. Each esolang creating a unique means of communicating with the computer that make sense only to esoprogrammers willing to bypass the niceties of mainstream computing.

Temkin approaches esolangs through an art crit lens. I think this is a valid one: the best ones make you think about things you take for granted. Just like good modern art does. And if you're lucky, they make you laugh in the process of educating you, like an IgNobel winning science paper.

[0] http://esoteric.codes/#_=_

[1] http://esoteric.codes/post/133863781313/the-less-humble-prog...

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)

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.

Awesome slides!!!

I'd heard of Piet, but never seen the primaltity tester. It really looks like a Mondrian!

Another thing I really like is Typogenetics, invented by Douglas Hofstadter. It's a formal system inspired by molecular biology and is almost definitely Turing complete (though I haven't looked for a proof).

That should be Nick Bostrom's face at the end there; not Elon Musk's.

Is there a talk associated with these slides? I bet it would be fascinating!

If you want references/links, I covered a lot of the same material in my page on 'accidentally Turing-complete' stuff: https://www.gwern.net/Turing-complete

I wish OP had had more slides on "Is Unicode Turing-Complete?" which is a terrifying question to even ask. Don't leave us hanging! Is it?!

Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact