As you know, most of the widely used programming languages ββ(especially imperative) are Turing-complete. And some even with respect to the compilation time, like, say, C ++ with their templates.
And how is Turing completeness proven / refuted? In itself, this concept looks difficult to formalize.
Formally, it is necessary to prove it from the point of view of the theory of recursive functions β a language is Turing-full if and only if it allows one to write every computable function. In practice, this is usually quite cleverly appealed to [Church's thesis]. ( Http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis )
See also β How to Prove a Programming Language is Turing Complete? ".
For some reason it seems to me that if we can implement a Turing machine in some language, this means that it is turing-complete. Although I could be wrong.
Source: https://ru.stackoverflow.com/questions/184333/
All Articles