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.

  • one
    ... and pragmatically - we take some simple Turing-complete language, for example, PL / 1, and see that all its constructions are expressible in a language that is interesting to us. - VladD
  • one
    (late addition) And BrainFuck is better, it is much easier. - VladD

2 answers 2

    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.