19
$\begingroup$

Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness.

However, pure Prolog is incapable of expressing list intersection. (Disequality, dif/2, would allow it to do it, but dif/2 is not Horn, unlike equality).

This seems like a paradox, at first glance. Is there a simple explanation?

Improve this question
$\endgroup$
9
  • $\begingroup$ pure Prolog is incapable of expressing list intersection I'm still not convinced that this is true. It is only true if you cannot enumerate the domain of the list members, sorted according for example the standard order of terms, because then you scan just can through the domain (runtime is not important, right?) and collect the terms which have hits in both lists. So yes, you can't do it in Prolog. Prolog is a bit problematic because it has neither sorts nor types nor enums, you never know what you have in front of you - it's like a bottomless pit everywhere. $\endgroup$
    – David Tonhofer
    Jan 2, 2021 at 23:33
  • 2
    $\begingroup$ Does it also seem paradoxical that Turing Machines can't "express list intersection" in the way you desire (since they can't even "express lists")? The solution in both cases, as mentioned by others, is that we can encode the desired behaviour using something the language does provide (e.g. Horn clauses, symbols on a tape, lambda functions, etc.) $\endgroup$
    – Warbo
    Jan 4, 2021 at 16:34
  • 1
    $\begingroup$ @MaxB Not really; AFAIK Prolog data is structured as terms; sometimes those terms can be unified against certain patterns, other times they can't. Cons cells are quite amenable to such structuring; appended-lists are less so; operations like intersection even less so. $\endgroup$
    – Warbo
    Jan 4, 2021 at 22:11
  • 1
    $\begingroup$ More data: 1) The only way t write a TM correctly in pure Prolog is to make iit 100% deterministic with causality going in reverse direction of the :- so that the proof search works as the stepper: One is actually asking "does this machine ever halt", and the head is the state at time T, whereas the body is the state at time T+1, and the decision which clauses to pick must be deterministic. The TM looks like: tm(T,Halt,TapeLeft,TapeHead,TapeRight,State) :- lookup(State,NewState,...),tm(s(T),Halt,NewTapeLeft,NewTapeHead,NewTapeRight,NewState). $\endgroup$
    – David Tonhofer
    Jan 6, 2021 at 18:22
  • 1
    $\begingroup$ While the above TM can compute "list intersection" of list of natural numbers using an appropriate program and is in Prolog, a pure Prolog program given two lists cannot - this means a pure Prolog program cannot transform a list of arbitrary ground terms (in particular numbers) into a binary representation on a TM tape. But why? Well, it cannot avoid generating spurious proof witnesses (no cuts, and since, there is no dif/2 , no guards - it will traverse the whole proof tree) and it cannot fall back to enumeration (no finite domains anywhere). Don't know how to make this idea precise... $\endgroup$
    – David Tonhofer
    Jan 6, 2021 at 18:28

2 Answers 2

Reset to default
82
$\begingroup$

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that.

A list is not a natural number, and list intersection is not a function on natural numbers.

Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a function on natural numbers. And I have no doubt that, given you chose a suitable encoding of lists, Pure Prolog will be perfectly capable of expressing list intersection.

To put it another way: just because Pure Prolog is not capable of expressing list intersection using the particular representation of lists that was chosen for General Prolog does not mean that there does not exist a representation of lists more suitable for use with Pure Prolog such that Pure Prolog is capable of expressing intersection of those particular lists.

Improve this answer
$\endgroup$
10
  • 23
    $\begingroup$ ..."It means exactly that and only that." Which is, regrettably, a detail that escapes most people who try to discuss them. $\endgroup$
    – Mark Morgan Lloyd
    Jan 2, 2021 at 20:13
  • 13
    $\begingroup$ Beware the turing tar pit my friends, where everything is equivalent, and nothing of interest is easy. $\endgroup$
    – Yakk
    Jan 2, 2021 at 23:25
  • 25
    $\begingroup$ @MarkMorganLloyd: Hence why, at least for pragmatic and practical purposes, the (slightly humorous) notion of "Tetris-completeness" is often more interesting: "Can I implement a game, meaning, can I write a (potentially infinite) game loop, have I/O, interact with the OS, interact with C libraries, and asynchronously react to an infinite stream of events, all within soft-realtime constraints?" $\endgroup$
    – Jörg W Mittag
    Jan 3, 2021 at 0:36
  • 4
    $\begingroup$ @JörgWMittag Oh, so like Conway's Game of Life? :P $\endgroup$
    – Spitemaster
    Jan 3, 2021 at 7:40
  • 12
    $\begingroup$ I suppose it's like trying to do reflection in C. "How come C is Turing-complete but it can't print out all the members of a struct?" $\endgroup$
    – user253751
    Jan 4, 2021 at 13:08
4
$\begingroup$

Expressiveness is not a criteria of being Turing complete. Computability is.

If Pure Prolog is Turing Complete then Pure Prolog can compute the intersection between two sequential sets.

You may not be able to express this computation. It may take you several lines of code or even several pages. You may not be able to use the data structure you prefer. You may need to resort to a different data structure to represent the list or even resort to files on disk. But it should be possible.

The definition of Turing completeness is strictly:

Being able to write a program that implements a Universal Turing Machine.

In other words:

If you can write a Universal Turing Machine emulator in it, it is Turing Complete!

Nothing more, nothing less.

The only reason this definition is considered useful is that for a given computable list of instructions (also called a "language" but most people these days would call it a "program"), there should be at least one Turing Machine capable of parsing it. And it is proven that you can write programs for a Universal Turing Machine that can emulate any Turing Machine. When combined, this means that a Universal Turing Machine can parse anything computable because even if it can't it can execute a Turing Machine eumlator that can parse that thing.

So the theoretical solution for any Turing Complete language incapable of performing a computation is to run a Universal Turing Machine emulator in that language and run a Turing Machine eumlator in that emulator to perform the given computation.

Of course, this is not practical. But Turing Completeness is not about practicality (nor is it about expressiveness), it is only about possibility. It is about computability.

Side note: I would like to bring to your attention the fact that there is a lot of things in computing that are what I call beyond Turing complete.

For example, modern OSes like Linux and Windows and iOS require a computing system that is beyond Turing complete - specifically they require interrupt support. It is possible to write a virtual CPU and run it on a CPU that cannot do interrupt and fake interrupts in software but doing so will fail to work real-time (note: there was a Unix workstation that did something like this but I forgot its name, the CPU did not have interrupts so the computer used two CPUs - one to run the programs and OS and another to monitor hardware and pause the main CPU to handle hardware events thus emulating hardware interrupts - but note that the system is essentially using a second full Turing Machine to implement the thing the main Turing Machine cannot do on its own).

Another example is the Top-Down Operator Precedence algorithm for implementing compilers/parsers. While it can be implemented with any language it is considerably easier to implement it with a language that has first-class functions, a features common in functional languages but uncommon in procedural languages. Heck, even functions themselves are beyond Turing complete since they're not part of Universal Turing Machines (though they form the core of Lambda Calculus - the other computing system developed to define computability and computing)

Improve this answer
$\endgroup$
5
  • $\begingroup$ These days we're so used to general computing devices like smartphones and laptops that we forget what the big deal about computability was. What Turing proved was that it is possible to design a general purpose computer instead of needing dedicated calculators for math, another machine to do accounting, another machine to draw maps, another machine to write emails etc. $\endgroup$
    – slebetman
    Jan 5, 2021 at 8:06
  • $\begingroup$ I get your point, but as this answer points out, you do need another machine to write emails, since the acts of writing and sending emails are interactive processes. $\endgroup$
    – Fax
    Jan 5, 2021 at 14:46
  • $\begingroup$ @Fax Maybe you've chosen to write emails on another machine but I write my emails on the same laptop I write code and run Photoshop. Way back when Turing was writing his thesis under Church we weren't really sure if this would be possible and even if some people thought so (Ada Lovelace certainly seemed to have the intuition that it would be possible several decades before Turing) we didn't have proof $\endgroup$
    – slebetman
    Jan 5, 2021 at 15:17
  • $\begingroup$ It's not possible to do what you do on your laptop on any machine that is Turing-complete. You need something more, and that's why writing emails is a bad example. It also undermines your computability point, since "expressiveness" is another example of "something more". $\endgroup$
    – Fax
    Jan 6, 2021 at 15:26
  • $\begingroup$ What is "first class"? (rhetorical) Functions aren't necessarily native to a CPU instruction set, they are implemented with stack frames and whatnot to formalise what is arguably no more or less than a rather good idiom. Aunty Ada invented the computer. All the rest is the work of compiler writers. $\endgroup$
    – Peter Wone
    Jan 6, 2021 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.