README
¶
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
- Introduction
- Section 1 - Computing machines
- Section 2 - Definitions
- Section 3 - Examples of computing machines
- Section 4 - Abbreviated tables
- Section 5 - Enumeration of computable sequences
- Section 6 - The universal computing machine
- Section 7 - Detailed description of the universal machine
- Section 8 - Application of the diagonal process
- Section 9 - The extent of computable numbers
- Section 10 - Examples of large classes of numbers which are computable
- Section 11 - Application to the Entscheidungsproblem
- Appendix - Computability and effective calculability
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.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.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DescriptionNumber ¶
type DescriptionNumber string
The StandardDescription converted uniquely to a number
type MConfiguration ¶
type MConfiguration struct {
// The possible behaviour of the machine at any moment is determined by the m-configuration qn...
Name string
// ...and the scanned symbol S(r)
Symbols []string
// In some of the configurations in which the scanned square is blank (i.e. bears no symbol)
// the machine writes down a new symbol on the scanned square: in other configurations it
// erases the scanned symbol. The machine may also change the square which is being scanned,
// but only by shifting it one place to right or left.
Operations []string
// In addition to any of these operations the m-configuration may be changed.
FinalMConfiguration string
}
An m-configuration contains four components
type Machine ¶
type Machine struct {
// contains filtered or unexported fields
}
Turing's Machine
func (*Machine) CompleteConfiguration ¶
Returns the machine's Complete Configuration of the single-line form
func (*Machine) MoveN ¶
Moves the machine n times and stops early if halted. Returns the amount of moves the machine took.
func (*Machine) TapeString ¶
Return the Tape represented as a string
func (*Machine) TapeStringFromUniversalMachine ¶
Helper function to isolate the computed sequence between the colons
type MachineInput ¶
type MachineInput struct {
// ...which is only capable of a finite number of conditions q1, q2, ..., qR which
// will be called "m-configurations".
MConfigurations []MConfiguration
// The machine is supplied with a "tape" (the analogue of paper) running through it,
// and divided into sections (called "squares") each capable of bearing a "symbol".
Tape Tape
// The m-configuration that the machine should start with. If empty the first m-configuration
// in the list is chosen.
StartingMConfiguration string
// A list of all symbols the machine is capable of reading or printing.
// This field is used when dealing with special symbols `*` (Any), `!` (Not)
// Note: The ` ` (None) symbol does not have to be provided (it is assumed).
PossibleSymbols []string
// Defaults to ` ` (None), but can optionally be overridden here.
NoneSymbol string
// If `true`, the machine's complete configurations are printed at the end of each move.
Debug bool
}
We may compare a man in the process of computing a real number to a machine...
func NewAbbreviatedTable ¶
func NewAbbreviatedTable(input AbbreviatedTableInput) MachineInput
Gives MachineInput for the abbreviated table. This requires "compiling" the abbreviated table.
func NewMachineFromDescriptionNumber ¶
func NewMachineFromDescriptionNumber(dn DescriptionNumber) (MachineInput, error)
Converts a D.N. to a Machine. Returns an error if the D.N. is not well-defined.
func NewUniversalMachine ¶
func NewUniversalMachine(input UniversalMachineInput) MachineInput
If `M` is a Machine that computes a sequence, this function takes the Standard Description of `M` and returns MachineInput that will print `M`'s sequence using `U` (the Universal Machine).
type StandardDescription ¶
type StandardDescription string
A string representing the full m-configuration list of a Machine
type StandardTable ¶
type StandardTable struct {
// The first is input to a machine that has been standardized.
MachineInput MachineInput
// The second is a mapping from our new symbols to our symbols.
// This is not essential but helps with debugging and testing.
SymbolMap SymbolMap
// Turing's Standard Description (S.D.)
StandardDescription StandardDescription
// Turing's Description Number (D.N.)
DescriptionNumber DescriptionNumber
}
Our StandardTable is a wrapper for Turing's standard forms
func NewStandardTable ¶
func NewStandardTable(input MachineInput) StandardTable
Standardizes MachineInput so it conforms to Turing's standard form.
type SymbolMap ¶
A map of new symbols to old symbols, used to verify Tape output
func (SymbolMap) TranslateTape ¶
Translates a tape to the original symbol set.
type Tape ¶
type Tape []string
Our "tape" is a slice of strings because squares can contain multiple characters
type UniversalMachineInput ¶
type UniversalMachineInput struct {
StandardDescription
SymbolMap
}
Input for the UniversalMachine
Source Files