Models of computation

1 Neural synthesis

See neural automata.

2 Physically grounded

N. A. Gershenfeld (2000)

The Physics of Information Technology explores the familiar devices that we use to collect, transform, transmit, and interact with electronic information. Many such devices operate surprisingly close to very many fundamental physical limits. Understanding how such devices work, and how they can (and cannot) be improved, requires deep insight into the character of physical law as well as engineering practice. The book starts with an introduction to units, forces, and the probabilistic foundations of noise and signalling, then progresses through the electromagnetics of wired and wireless communications, and the quantum mechanics of electronic, optical, and magnetic materials, to discussions of mechanisms for computation, storage, sensing, and display. This self-contained volume will help both physical scientists and computer scientists see beyond the conventional division between hardware and software to understand the implications of physical theory for information manipulation.

Same author, possibly more compact: Neil Gershenfeld (2011), N. Gershenfeld (1996).

3 Everything is Turing-complete

Unusual computers - Interesting Esoterica

Surprisingly Turing Complete

Many configuration or special-purpose languages or tools or complicated games turn out to violate the Rule of least power & be “accidentally Turing-complete”, like MediaWiki templates, sed or repeated regexp/find-replace commands in an editor (any form of string substitution or templating or compile-time computation is highly likely to be TC on its own or when iterated since they often turn out to support a lambda calculus or a term-rewriting language or tag system e.g. esolangs “///” or Thue ), XSLT, Infinite Minesweeper, Dwarf Fortress3, Starcraft, Minecraft, Ant, Transport Tycoon, C++ templates & Java generics, DNA computing etc are TC but these are not surprising … On the other hand, the vein of computer security research called “weird machines” is a fertile ground of “that’s TC?” reactions. What is “surprising” may differ from person to person.

• Peano arithmetic: addition & multiplication on natural numbers is enough to be TC; in contrast, Presburger arithmetic removes multiplication and hence is not TC

• Wang tiles: multi-colored squares, whose placement is governed by the rule that adjacent colors must be the same (historically, not surprising to Wang, but was surprising to me and I think to a lot of other people)

• X86 shenanigans:

• MMU shuffle computer RAM around to make programming easier; if a program sets up its share of memory properly, it can execute arbitrary computations via MMU page-faults without ever running code itself by turning the MMU faulting mechanism into a one-instruction set computer.

• “mov is Turing-complete”: the apparently innocuous x86 assembler instruction mov, which copies data between the CPU & RAM, can be used to implement a transport-triggered-architecture one instruction set computer, allowing for playing Doom (and for bonus points, it can be done using xor too)

• “x86 is Turing-complete with no registers” […]

• musical notation: given instructions for transposing successive notes, musical notation becomes the esolang Choon

• heart cells: interact in a way allowing logic gates and hence TC (perhaps not too surprising since cellular automatons were biologically motivated)

• one category of weird machines doesn’t quite count since they require an assumption along the lines of the user mechanically clicking or making the only possible choice in order to drive the system into its next step; while the user provides no logical or computational power in the process, they aren’t as satisfying examples for this reason:

• Magic: the Gathering: TC, with the assumption that players mechanically take any option they are given, but otherwise all actions/plays are forced by Magic rules

• CSS: was designed to be a declarative markup language for tweaking the visual appearance of HTML pages, but CSS declarations interact just enough to allow an encoding of the cellular automaton Rule 110, under the assumption of mechanical mouse clicks on the web browser to advance state

• Microsoft PowerPoint animations (excluding macros, VBScript etc) can implement a Turing machine when linked appropriately (Wildenhain 2017; video; PPT), under the assumption of a user clicking on the only active animation triggers.

4 Weird stuff

John Shutt’s weird λ-calculus-based approaches to superunification:

A more straightforward solution, […] is to give up on chronological determinism and instead acquire mathematical determinism, by the arguably “obvious” strategy of supposing that the whole of spacetime evolves deterministically along an orthogonal dimension, converting unknown initial conditions (initial in the orthogonal dimension) into chronological nondeterminism. […]

The approach does, however, seem well-suited to a co-hygiene-directed theory. Church-Rosser-ness implies that term rewriting should be treated as reasoning rather than directly as chronological evolution, which seemingly puts term rewriting on a dimension orthogonal to spacetime. The earlier co-hygiene post noted that calculi, which converge to an answer via Church-Rosser-ness, contrast with grammars, which are also term-rewriting systems but exist for the purpose of diverging and are thus naturally allied with mathematical nondeterminism whereas calculi naturally ally with mathematical determinism. So our desire to exploit the calculus/physics analogy, together with our desire for abstract separability of parts, seems to favor this use of a rewriting dimension orthogonal to spacetime.

I bet Hackernews weighs in enthusiastically on this.

5 Rewriting Systems

Especially string rewriting but you can do almost-anything rewriting.

• Semi-Thue systems
• Rewriting home page
• Emile Post’s Tag machines

6 References