Scatter machines bounded in space
Em: Handbook of Unconventional Computing
Editor: World Scientific, Singapura
Vol: Vol. 1
Páginas: 59-97
Resumo:
We studied deterministic Turing machines with access to oracles that give imprecise answers and take time to consult (on the size of the queries) to model situations where computers process sensor data from their environment. The imprecision of the oracle gives rise to probabilistic behaviour of Turing machines. Turing machines clocked in polynomial time were classified according to the degree of precision provided by the analogue oracle. In this chapter we attempted to repeat our previous study, but now addressing bounded resources in space. We present a characterization of Turing machines bounded in polynomial space having access to stochastic timed oracles into computational classes depending on the pecision of the oracle or, in another way, the analogue-digital protocol.