0
$\begingroup$

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input word?

$\endgroup$
  • $\begingroup$ Don't you see a problem with this definition in case of very large inputs? $\endgroup$ – diplodoc Nov 11 '19 at 9:11
0
$\begingroup$

According to the WP article on Turing machine equivalents, oblivious machine head position is independent of input and is a function of time instead. To wit:

An oblivious Turing machine is a Turing machine where movement of the various heads are [sic] 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.

REFERENCES

https://dl.acm.org/citation.cfm?doid=322123.322138

SEE ALSO

Head Position Function of Oblivious Turing Machines
https://stackoverflow.com/questions/14847080/how-does-an-oblivious-turing-machine-work

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.