Oblivious Turing machines
An oblivious Turing machine is a Turing machine where movement of the various heads are fixed functions of time, independent of the input. In other words, there is a predetermined sequence in which the various tapes are scanned, advanced, and written to. Pippenger and Fischer (1979) showed that any computation that can be performed by a multi-tape Turing machine in n steps can be performed by an oblivious two-tape Turing machine in O(n log n) steps.
posted on 2012-02-15 03:53
luis 阅读(601)
评论(0) 编辑 收藏 引用 所属分类:
人工智能