Web Machines

• A web machine is a Turing machine with 3 tapes

  • a right-infinite input tape
  • a two-way infinite work tape
  • a right-infinite output tape

• Initially the input tape contains the encoding of the current web, other tapes are empty

• The output tape head can only move to the right, all other heads can move both ways

• Encode a web instance as

Previous slide

Next slide

Back to first slide

View graphic version