[Solved]: How close are common programming languages to not being Turing complete?

Problem Detail: 

The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually requires. I found this question, but the answers are a bit more mathematical than what I am looking for.

Take a common programming language, such as C++, Python, Java or Lisp. How close are these languages to being not Turing complete? Do these languages have elementary features that if removed would make the language not Turing complete? Or could you change a property of the language (for example, making something random) and by doing that make the language not Turing complete?

Asked By : Aqwis

Answered By : Gilles

Common programming languages are very firmly Turing-complete, if you take an idealized view where programs can use an arbitrary large amount of memory. There typically isn't a single feature that you can isolate without which the language wouldn't be Turing-complete.

Intuitively speaking, Turing completeness requires two things:

• A way for programs to manipulate an amount of memory that doesn't solely depend on the size of the input. Any form of object creation that can build bigger objects from smaller objects is suitable: objects, structures, pairs, lists, malloc, new, etc. Even stack-based allocation is enough provided that there is a way to access objects at any distance from the top of the stack (with only stack-based allocation and only access to the top of the stack, you only get a pushdown automaton). Many weaker forms of data manipulation are also suitable: for example, in a language like Lisp or Python where integers don't have a limited size, the basic integer operations alone are enough for Turing completeness.
• A way for programs to keep running or halt based on some part of the data. While loops, recursion plus some form of conditional (e.g. if or case/switch) and goto plus some form of conditional are the three common ways, but there are others.

I think that the best way to understand what makes a language Turing-complete is to look at examples of languages that are powerful, but not Turing-complete. I'll give two examples that illustrate the two main families of such languages (other than languages that operate in bounded memory).

Consider an imperative language with integer operations and arrays, but only for loops (for i = 1 to n, where i cannot be modified during the loop), not arbitrary (while) loops and no recursion. BlooP and early versions of FORTRAN are examples. In such a language, you can only express primitive recursive functions — functions where the amount of computation is bounded in the size of the input. The language is not Turing-complete — cannot express arbitrary recursive functions — because of the bound on computation time.

A functional language can be made non-Turing-complete by restricting recursion through a type system that restricts all functions to be terminating. If the type system is decidable (i.e. if it is decidable whether the program is well-typed), then such a language cannot be Turing-complete (because the halting problem is undecidable). Languages used for theorem proving, such as Coq and Agda, are of this kind.

See also What can Idris not do by giving up Turing completeness?

---

On a side note, theorem provers require the user to input termination proofs (i.e. they don't find them themselves). So you could make a theorem prover with an undecidable type system: if you get a correct proof accepted, you're happy, otherwise you give up after a while. But it wouldn't be user-friendly. Most theorem provers have a decidable type system: you enter a term, and either it's accepted or you get a type error back. What theorem provers don't have is decidable type inference: if you type a term with partial type information and it's rejected, you don't know whether it's because the term cannot be typed or because the inference engine wasn't smart enough.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19676