According to 1 (probably not the most relevant source), propositional logic is not Turing complete. Aren't all computations in computers performed using logic gates, which can be represented as logical operators, though? Is it maybe because logic has no memory while a Turing machine does? What kind of computations is propositional logic unable to perform?

  • $\begingroup$ Physical computers are not Turing complete either, actually: they only have finite memory, unlike a Turing machine. $\endgroup$ – Zhen Lin Apr 1 '13 at 19:14
  • $\begingroup$ I've heard about this, but they can be considered to be Turing complete for practical purposes, correct? In that they can perform any computation that a Turing machine can up to a memory limit. $\endgroup$ – Hypercube Apr 1 '13 at 19:17
  • 2
    $\begingroup$ Yes, but Turing completeness is a theoretical condition, not a practical one. For instance, taking a literal reading of the definitions, the halting problem is decidable for any (idealised) physical computer, because it is a finite state machine! $\endgroup$ – Zhen Lin Apr 1 '13 at 20:10
  • $\begingroup$ IHMO I think that Tunring's model of computation did not required infinite memory. As far as I remember The original paper talks about "unbounded" tape (see eprints.gla.ac.uk/4481/1/4481.pdf?ref=Sex%C5%9Ehop.Com page 3 for a discussion). This means that the length of the tape is unknown a priory but not infinite. $\endgroup$ – JuanPi May 31 '14 at 22:49

Aren't all computations in computers performed using logic gates, which can be represented as logical operators, though?

Using logic gates with feedback. Using only propositional logic it's impossible to express arbitrary repetition, i.e., using the same subformula multiple times. In programming terms, this means no loops, recursion, jumps, or anything similar. Memory is also an issue, but without a means of repetition even with some notion of unbounded memory you'd only be able to use a fixed amount of it.

Propositional logic is among the computationally weakest systems that anyone actually cares about, being unable to even express basic arithmetic (i.e., with numbers of arbitrary size, as opposed to the fixed size of something like an 8-bit adder) on its own.

What kind of computations is propositional logic unable to perform?

Most of them!

As far as Turing-completeness goes, that essentially means "the ability to perform computations which we're not sure will ever finish", but there's a huge range of computations that are known to always finish but which propositional logic can't express.

A good example of another (relatively weak) system that people care about is recognizing regular languages. You can't express this in propositional logic because the input size is variable, and even if you set a hard limit on the input size the best you can do in general is to have a formula that computes a massive OR of subformulas to recognize each possible matching string.

  • $\begingroup$ Thank you for the detailed answer. By feedback you mean sequential circuits, right? $\endgroup$ – Hypercube Apr 1 '13 at 20:25
  • $\begingroup$ @Hypercube: I mean circuits where an input to a gate can logically depend on its own output. For example, flip-flops implement simple memory cells using feedback loops. $\endgroup$ – camccann Apr 1 '13 at 20:52

"Keep searching until you find an example."

(E.g., is there an even number that is not a sum of two primes? It's easy to check in each case, so keep going until you meet one.)

Construe the first sentence above as an instruction in a programming language. It's just that statement that cannot be done in the limited programming language you propose.

One way of defining computability says the computable functions start with the zero function, the successor functions, and the projection functions, and are closed under composition, primitive recursion, and minimalization. The last operation---minimalization---consists of just searching until you find some specified thing and returning as output the number of steps it takes. There's a diagonal argument that shows that the functions you get without including minimalization (called the "primitive recursive functions") fail to include all computable functions. When you add minimalization, you add the risk that the search might run forever. (In the concrete example above, it runs forever if Goldbach's conjecture is true.) So you get some functions that are not everywhere defined. The fact that they're not everywhere defined is just the thing that prevents the same diagonal argument from working on the new class of functions that you get, to show that they also fail to contain everything.


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.