Computable Secrets

Lab / Turing machine

Turing machine simulator

Define a machine, give it a tape, and watch it run. Machines can use several tapes, and a document with stages separated by --- runs them as a pipeline, each stage's tape feeding the next. "Copy share link" turns the whole experiment into a URL.

Sign in to save machines by name.

Library

Tested machines to start from — load one, run it, take it apart.

  • Binary increment

    Adds one to a binary number: walk to the end, then carry leftward.

  • Palindrome checker

    Two tapes: copy the input, then read it forward against backward. Accepts exactly the palindromes over a, b.

  • Reverse

    Two tapes: copy, rewind, then write the copy back in reverse.

  • Swap a and b

    One tape: flip every a to b and back, then rewind. Compose it with itself and you get the identity.

  • Add two (a pipeline)

    Composition: two increment machines separated by ---. The first stage's tape becomes the second stage's input.

Format
name: <text>              # optional; labels the stage in a pipeline
start: <state>            # required; heads start on the first input cell
accept: <state>, ...      # optional; entering one halts and accepts
blank: <symbol>           # optional; default _
tapes: <n>                # optional; inferred from the rules (max 4)

<state>, <read> -> <state>, <write>, L|R|S
q, a|_ -> q, a|a, R|R     # multi-tape: fields separated by |

---                       # composition: stages run in sequence;
                          # a stage must accept to hand its tape on

# '#' starts a comment. Symbols are single printable characters.
# A machine halts when no rule matches; that accepts only in an
# accept state. Runs share a budget of 20,000 steps.