The University of Sussex

Simulating Turing machines in DATR

Lionel Moser

In this paper we show how an arbitrary Turing machine can be simulated in DATR, and show that the computational complexity of DATR is Turing equivalent - and hence termination of query evaluation is undecidable.


Download zip file