Show HN: A reference implementation of Turing's paper “On Computable Numbers”

Turing

The first complete and open source implementation of Alan Turing's famous 1936 paper - On Computable Numbers, with an Application to the Entscheidungsproblem.

Why?

About a month ago I attempted to read Turing's paper, and found it too difficult to understand. I figured reading a reference implementation (that includes m-functions, a working univeral machine, etc.) would make things clearer. It was super surprising to find that a full implementation does not exist on the internet, so I decided to write my own.

Guide

For those who intend to read the full paper I recommend starting with The Annotated Turing by Charles Petzold (which explains the paper line-by-line with annotations).

I wrote a section-by-section guide (GUIDE.md) that explains the paper in the context of this codebase. My hope is that the combination of a reference implementation and walkthrough helps others get value from the paper like I did.

Progress

Usage

For those who want to use the implementation, here is how to get started:

go get github.com/planetlambert/turing@latest

import (
    "fmt"

    "github.com/planetlambert/turing"
)

func main() {
    // Input for Turing Machine that prints 0 and 1 infinitely
    machineInput := turing.MachineInput{
        MConfigurations: turing.MConfigurations{
            {Name: "b", Symbols: []string{" "}, Operations: []string{"P0", "R"}, FinalMConfiguration: "c"},
            {Name: "c", Symbols: []string{" "}, Operations: []string{"R"},       FinalMConfiguration: "e"},
            {Name: "e", Symbols: []string{" "}, Operations: []string{"P1", "R"}, FinalMConfiguration: "k"},
            {Name: "k", Symbols: []string{" "}, Operations: []string{"R"},       FinalMConfiguration: "b"},
        },
    }

    // Construct the Turing Machine and move 50 times
    machine := turing.NewMachine(machineInput)
    machine.MoveN(50)
    
    // Prints "0 1 0 1 0 1 ..."
    fmt.Println(machine.TapeString())

    // Convert the same Machine input to Turing's "standard" forms
    standardTable := turing.NewStandardTable(machineInput)
    standardMachineInput := standardTable.MachineInput
    symbolMap := standardDescription.SymbolMap
    standardDescription := standardTable.StandardDescription
    descriptionNumber := standardTable.DescriptionNumber

    // Also prints "0 1 0 1 0 1 ..."
    standardMachine := turing.NewMachine(standardMachineInput)
    standardMachine.MoveN(50)
    fmt.Println(machine.TapeString())

    // Prints ";DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA"
    fmt.Println(standardDescription)

    // Prints "73133253117311335311173111332253111173111133531"
    fmt.Println(descriptionNumber)

    // Construct Turing's Universal Machine using the original Machine's Standard Description (S.D.)
    universalMachine := turing.NewMachine(turing.NewUniversalMachine(turing.UniversalMachineInput{
        StandardDescription: standardDescription,
        SymbolMap:           symbolMap,
    }))

    // Turing's Universal Machine is quite complex and has to undergo quite a few moves to achieve the same Tape
    universalMachine.Move(500000)

    // Prints "0 1 0 1 0 1 ..."
    fmt.Println(universalMachine.TapeStringFromUniversalMachine())
}

Go Package Documentation here.

FAQ

• Why Go?
  • I like Go, and it is the most readable language for me currently.
• How is the performance?
  • My goal for this repository is to be a learning resource, so when possible I bias towards readability.

from Hacker News https://ift.tt/svFRCGH