Skip to content

A reference implementation of Alan Turing's 1936 paper, On Computable Numbers

License

Notifications You must be signed in to change notification settings

planetlambert/turing

Repository files navigation

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?

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, but was surprised to find that a full implementation does not exist on the internet. I thought it could be fun to try 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 := standardTable.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.MoveN(500000)

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

Go Package Documentation here.

Testing

go test ./...

FAQ

  • Why Go?
    • I like Go and I think its easy to read.
  • How is the performance?
    • My goal for this repository is to be a learning resource, so when possible I bias towards readability.

About

A reference implementation of Alan Turing's 1936 paper, On Computable Numbers

Topics

Resources

License

Stars

Watchers

Forks

Languages