Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what abstract machine does it model?

  • $\begingroup$ Not sure about the tags; feel free to change them. $\endgroup$ – Filip Haglund Oct 9 '16 at 12:24
  • 4
    $\begingroup$ Damnit, if Datalog and Chomsky deserve capital letters, I'm pretty sure Alan Turing does. He only invented the whole thing we study... I don't know why we get so many questions here with lower-cased "turing". $\endgroup$ – David Richerby Oct 9 '16 at 13:14
  • $\begingroup$ @DavidRicherby Turing did so much that the word is so common it's barely a name anymore. Maybe it's the ultimate honour to have your name lowercased. Do you still capitalize "internet"? :) $\endgroup$ – Filip Haglund Oct 9 '16 at 13:30
  • $\begingroup$ I don't know about David. I do capitalize Internet. I also capitalize Computer Science, Mathematics and Academia. Also, I am an Ada programmer. $\endgroup$ – scaaahu Oct 9 '16 at 13:33
  • 1
    $\begingroup$ @FilipHaglund I don't capitalize "internet", no, because it is no longer considered to be a proper noun. I capitalize Turing because it is indisputably a proper noun: it is a person's name. $\endgroup$ – David Richerby Oct 9 '16 at 14:55

According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine or an EXPTIME RAM machine.


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.