Why is propositional logic not Turing complete?

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.

Tags:

Turing Machines

Logic

Propositional Calculus

Related

Finding the inverse Laplace transform of $\arctan \left(\frac{1}{s} \right)$using contour integration Calculating $\lim_{n\to\infty}\sum_{k=1}^{\infty}\frac{(-1)^{k}\arctan(n^{2}k)}{n^{\alpha}+k^{3/2}}$ Convergence of Infinite Series Find the value of : $\lim_{x\to\infty}x\left(\sqrt{x^2-1}-\sqrt{x^2+1}\right)=-1$ Proving that $C$ is a subset of $f^{-1}[f(C)]$ If A is a denumerable set, and there exists a surjective function from A to B, then B is denumerable Approximation of $\mathrm{Li}(x) = \int\limits_{0}^x \frac{dt}{\ln t}$ Intuitively, why is the Gaussian the Fourier transform of itself? Series $\sum_{k=1}^\infty \left(\frac{1}{k}-\frac{1}{k+z} \right)$ The annihilator of an intersection is the sum of annihilators Prove that if the sum of each row of $A$ equals $s$, then $s$ is an eigenvalue of $A$. Why are triangles, squares and hexagons the only polygons with which it is possible to tile a plane?

Recent Posts