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 閱讀(627)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
人工智能