Abstract
In a previous paper, we used Maurer machines to model and analyse
micro-architectures.
In the current paper, we investigate the connections between Turing
machines and Maurer machines with the purpose to gain an insight into
computability issues relating to Maurer machines.
We introduce ways to simulate Turing machines on a Maurer machine which,
dissenting from the classical theory of computability, take into account
that in reality computations always take place on finite machines.
In one of those ways, multi-threads and thread forking have an
interesting theoretical application.
Preprint available here.