The term “Turing Complete” refers to a completely theoretical device known as a “Turing Machine”. It was initially described as a “Universal Machine” by the father of modern computing (Alan Turing) in his paper “On Computing Numbers” in 1936 (R1). This machine can compute “the same set of functions as a universal quantum computer, which can simulate any physical system”; thus it can theoretically solve any computational problem. (R2)
In Web3, the term is often used to describe modern programming languages (JavaScript, Python, C++, etc.) and their programs. A program is considered to be “Turing Complete” when it can replicate a Turing Machine by running any program the Turing Machine could run and/or solve. (R3) However, “whether a language is fully Turing complete vs. linearly bounded isn’t a very useful distinction, because we run our programs on computers of finite size and speed, not within the boundless logic-sphere of mathematics” (R4)
Example: Ethereum is considered to be Turing Complete because it needs to understand any future smart contract (even ones that have not been written yet). In other words, Ethereum’s “Turing Completeness means that it is able to use its code base to perform virtually any task, as long as it has the correct instructions, enough time and processing power.” (R3)
References:
R1: https://www.historyofinformation.com/detail.php?id=619
R2: https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf
R3: https://academy.binance.com/en/glossary/turing-complete
R4: https://evinsellin.medium.com/what-exactly-is-turing-completeness-a08cc36b26e2