Computational Completeness of Interaction Machines and Turing Machines
Peter W. Wegner, Eugene Eberbach, Mark Burgin · EPiC series in computing · 2018
In the paper we prove in a new and simple way that Interaction machines are more powerful than Turing machines. To do that we extend the definition of Interaction machines to multiple interactive components, where each component may perform simple computation. The emerging expressiveness is due to the power of interaction and allows to accept languages not accepted by Turing machines. The main result that Interaction machines can accept arbitrary languages over a given alphabet sheds a new light to the power of interaction. Despite of that we do not claim that Interaction machines are complete. We claim that a complete theory of computer science cannot exist and especially, Turing machines or Interaction machines cannot be a complete model of computation. However complete models of computation may and should be approximated indefinitely and our contribution presents one of such attempts.