Skip to main content
3 of 3
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/

Because we can easily invent as many small variations of Turing-complete models of computation as we like (see comments below the question), an answer to this question should try to concentrate on relevant (and Turing-complete) models, i.e. models that have either been investigated in illuminating non-trivial ways, or are important for better understanding of actually available computing resources.

I have been exposed in non-trivial ways to tape based Turing machines, register machines and pointer machines. It seem like the wikipedia article on abstract machines is intended to give an overview for related Turing machine equivalent models, but in its current form it is mainly a collection of useful keywords and links.


I'm currently looking for models and investigations related to machines limited to write once read many (WORM) memory for large amounts of data. None of the abstract machine models I found so far investigated these. Is it possible to create a model of such a machine that is equivalent to a Turing machine in the sense of the question above? (Edit: It looks like it was proved recently that Wang B-machines achieve this. I haven't read the paper yet.) This question seems to be both non-trivial and interesting to me, contrary to the comments below the question, which is the main reason why I wrote this answer.

Thomas Klimpel
  • 2.5k
  • 21
  • 41