The term \"Turing completeness\" has been discussed in several of the Computer S

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.