Turing's World: Table of Contents

• How to Use this Book
  • About the book
  • To the individual user
  • To the classroom user
  • Acknowledgements

• 1 About Turing Machines
  • 1.1 What can't computers do?
  • 1.2 Gödel's Theorem
  • 1.3 Turing machines
  • 1.4 Other machines
  • 1.5 Further reading

• 2 Running Turing Machines
  • 2.1 Starting up Turing's World
  • 2.2 Opening a tape from a file
  • 2.3 Running a Turing machine
  • 2.4 Opening a machine from a file
  • 2.5 Stepping through a computation
  • 2.6 Resetting a machine
  • 2.7 Writing directly on the tape
  • 2.8 Getting frozen: when nothing works
  • 2.9 Seeing more of the tape
  • 2.10 Quitting
  • 2.11 Looking at a submachine
  • 2.12 Pausing and changing speed in mid-run
  • 2.13 Computational complexity
  • 2.14 Seeing more of the state diagram
  • 2.15 Saving design time with submachines

• 3 Building Turing Machines
  • 3.1 Getting ready to build a machine
  • 3.2 Using the default alphabet
  • 3.3 Using the tool palette
  • 3.4 Setting up a tape
  • 3.5 Running the machine
  • 3.6 Summary of tape
  • 3.7 Moving windows
  • 3.8 Doing things during a computation
  • 3.9 Saving a state diagram
  • 3.10 Changing the start state
  • 3.11 Stopping a runaway Turing machine
  • 3.12 Using a custom alphabet

• 4 Editing a State Diagram
  • 4.1 Editing text
  • 4.2 Moving text
  • 4.3 Moving and editing arcs
  • 4.4 Moving and editing nodes
  • 4.5 Editing with the selection rectangle

• 5 Using Submachines
  • 5.1 Expanding a node into a submachine
  • 5.2 Moving and sizing submachine windows
  • 5.3 Shrinking the main machine
  • 5.4 Cutting or copying a submachine
  • 5.5 Editing a submachine
  • 5.6 Doing too much with a submachine

• 6 Other Features of Turing's World
  • 6.1 Debugging a Turing machine
  • 6.2 Using the wild card in arc labels
  • 6.3 Schematic machines
  • 6.4 Using 4-tuples to describe machines
  • 6.5 Making room for large state diagrams
  • 6.6 Printing

• 7 Other Kinds of Machines
  • 7.1 Finite state machines
    • One-way finite state machines
    • Acceptance nodes
    • Two-way finite state machines
  • 7.2 Nondeterministic machines
    • Nondeterministic finite state machines
    • The process tree
    • Nondeterministic Turing machines

• 8 Additional Exercises and Projects
  • 8.1 Finite state machines
  • 8.2 Turing machines
  • 8.3 Numerical computation
  • 8.4 Recursive functions
  • 8.5 The busy beaver function
  • 8.6 The Halting Problem
  • 8.7 Universal Turing machines
  • 8.8 Computability and logic
  • 8.9 Nondeterministic machines

Acknowledgements.

Return to Logic Software from CSLI.