Queries on Web Machines

• The output q(I) of a query q on input I is a set of objects

that are in some random order

• The output will be denoted by enc?(q(I))

• A query q is 0-computable is there exists a Web machine which on input enc?(I) halts and produces enc?(q(I)) on the output tape, for each I in inst(Web) and each ?.

• Every 0-computable query produces a finite output. Why?

Previous slide

Next slide

Back to first slide

View graphic version