Browser machine

• The browser machines contains

  • an infinite browsing tape
  • an infinite work tape
  • a right-infinite output tape
  • the expand state replaces an object identifier with its finite description (i.e. references and value)

• A query q is computable by a browser machine if there exists a browser machine on input (o,I) halts and produces on the output tape the encoding of q(o,I)

• Theorem 1. Every generic and computable Web query is browser computable.

Previous slide

Next slide

Back to first slide

View graphic version