[citation needed] Real computers constructed so far can be functionally analyzed like a single-tape Turing machine (which uses a "tape" for memory); thus the associated mathematics can apply by abstracting their operation far enough.
However, real computers have limited physical resources, so they are only linear bounded automaton complete.
The Church–Turing thesis states that this is a law of mathematics – that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can.
Charles Babbage's analytical engine (1830s) would have been the first Turing-complete machine if it had been built at the time it was designed.
[citation needed] From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing-complete.
In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions.
Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable,[9] thus identifying the computational core of the incompleteness theorem.
However, in 1998, it was shown by Rojas that the Z3 is capable of simulating conditional jumps, and therefore Turing complete in theory.
The first result of computability theory is that there exist problems for which it is impossible to predict what a (Turing-complete) system will do over an arbitrarily long time.
This would imply that no computer more powerful than a universal Turing machine can be built physically.
Here are a few: Most programming languages (their abstract models, maybe with some particular constructs that assume finite memory omitted), conventional and unconventional, are Turing-complete.
Most programming languages are describing computations on von Neumann architectures, which have memory (RAM and register) and a control unit.
[15][16] Turing completeness in declarative SQL is implemented through recursive common table expressions.
This illustrates one reason why relatively powerful non-Turing-complete languages are rare: the more powerful the language is initially, the more complex are the tasks to which it is applied and the sooner its lack of completeness becomes perceived as a drawback, encouraging its extension until it is Turing-complete.
The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.
Further examples include some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions.