Models of computation

Everything is Turing-complete

Unusual computers - Interesting Esoterica

Surprsingly 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 (comments; paper) 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

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 over-enthusiastically on this.

Rewriting Systems

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

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

Incoming