0
$\begingroup$

This question already has an answer here:

I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language.

For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of variables). That gives an easy way to say if a language is Turing complete, as soon as we've found out that it is imperative.

Hence my question is there any similar, characterization of Turing completeness which would work for any language?

$\endgroup$

marked as duplicate by Raphael Nov 7 '16 at 10:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

It seems very unlikely that there is any useful characterization other than the definition. Any such characterization would have to deal with all kinds of programming languages (imperative, functional, declarative and everything else) along with, assuming the claims from the Wikipedia article you link are correct, Minesweeper, Conway's game of Life and Magic the Gathering.

If you did have a characterization, it would probably be no easier to apply that characterization than to just apply the definition.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.