Irrelevant Topics IV

in Physics

Travis Hoppe
(deck source)


Esoteric Programming Languages

Computer Science


Board Games, Physics

Esoteric programming languages

Not your grandpa's Turing machine

Esolang and You

Why learn an esoteric language?

  • To push the boundaries of code/computation.
  • Examine the fundamental idea of an algorithm.
  • Has been done before with information, cf. Shannon.
  • Test computability, are non-computable ideas unphysical?
  • Central Irrelevant Topics Paradigm: Divide by zero.

Grandpas Turing Machine

A infinite "tape" of finite symbols.

A "head" with an internal state that
can advance only one spot at a time.

A finite set of instructions:
given a state and symbol perform set action.

Church Turing:

Every Universal Turing Machine is equivalent to every other

Turing Complete

Once a language can be shown to be similar to the tape-machine it is identical from a computational standpoint to any other.

Turing Tar Pits

  • Embody the idea of Turing's original tape machine.
  • (very) Limited set of instructions.
  • (very) Limited set of symbols.
  • Create obfuscated, impossible to maintain codes.
  • Extremely simple compilers.
  • Serves as a model to construct higher-order languages.


  • Extension of one-dimensional Turing tape machine.
  • Live in metric spaces with coordinate systems.
  • Usually Cartesian, but not necessarily.
  • Considered a "funge" if topology is toroidal.
  • More exotic topologies are classified as fungeoids.


  • Extreme minimalism: Turing tarpit
  • Designed to challenge and amuse programmers
  • Not suitable for practical use
  • Smallest compiler only 200 bytes!

Brainf*ck Instruction Set

  • > increment the data pointer
  • < decrement the data pointer
  • + increment the byte at the data pointer
  • - decrement the byte at the data pointer
  • . output the value of the byte at the data pointer
  • [ if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
  • ] if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.
  • , accept one byte of input, storing its value in the byte at the data pointer.

Brainf*ck Sample Code

Hello World


The first line initializes a[0] = 10 by simply incrementing ten times from 0. The loop from line 2 effectively sets the initial values for the array: a[1] = 70 (close to 72, the ASCII code for the character 'H'), a[2] = 100 (close to 101 or 'e'), a[3] = 30 (close to 32, the code for space) and a[4] = 10 (newline). The loop works by multiplying the value of a[0], 10, by 7, 10, 3, and 1, saving the results in other cells. After the loop is finished, a[0] is zero. >++. then moves the pointer to a[1] which holds 70, adds two to it (producing 72 which is the ASCII character code of a capital H), and outputs it.


  • Stack-based, Turing-tape style language.
  • Programs are arranged on a two-dimensional grid.
  • Tape has the topology of a toroid.
  • Arrow instructions direct the control flow.
  • Loops are constructed by sending the control flow in a cycle.
  • Befunge is a proper funge, and higher dimensional funges exist such as Trefunge.

Befunge Sample Code

Hello World

vv  <      <
    ^  v<
    ^   ^
>  >?>  ?>5^
    v   v
    v  v<
 .  >  >   ^


  • Ignores all characters but whitespace.
  • Each whitespace combination forms a bit-pattern.
  • Whitespace can be a polyglot.
  • Stenographic capabilities.
  • Challenges the idea of symbol and tape instructions.
  • Proof of Turning completeness is now CS homework.

Whitespace Sample Code

Hello World

 Say Hello

Non deterministic languages

Given the state of the program: the next action is taken
according to a probability distribution

Getting even trivial programs to have a reliable output is often a monumental task. Useful for exploring large search spaces, quantum computing, machine learning, ...

  • Unreliable (a feature not a bug!)
  • What is the notion of computability for a ND machine?
  • Expectation values of computability, Turing is a special case
  • Is Godel's incompleteness theorem even valid?

Chutes and Ladders

overthinking a classic

How many ideas of physics can be
expressed under the C&L topology?

Energy Landscapes

Chutes and Ladders Potential Function?

C&L does not possess a typical energy landscape; rather it is a stochastically driven process with discrete jumps.

Markov Chains

Used to represent transitions along discrete states, assumes
time-invariance. represents the probability from
state , and .

Single player Game Length Attention Span

Ergodic chain distributions

let the board become a loop, and look for steady state

Approaching steady state

, , , , ,

Differential Operators over C&L

Exponential Maps, and flows give rise to a differential-mapping. A set of coupled first-order differential equations has a natural connection to Markov chains:

The Markov matrix is the generator of the rate matrix at a given time:

Continuous-Time C&L

Assume that the die rolls now represent rates (like a chemical equation), i.e. the first roll would be:

This system of equations can be exponential to give a continuous-time Markov game.



Note the abissica on the second picture,
we are modeling fractions of a die roll!