Why is propositional logic not Turing complete?

Question

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?

Answer 1

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.

Answer 2

"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.