Talk:Turing completeness

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Top rated as Top-importance on the assessment scale

Contents


I suggest that people look at the articles for Turing Reduciblity and Turing Degree for a good understanding of the exact mathematical definition of Turing Complete and Turing Equivalence (which are different things!). The main problem I see is that Turing Complete has become a casual term for the most part, and it has lost most of its technical mathematical meaning among non-computer scientists (yes, you are free to read that as me being frustrated that tech people, geeks, and programmmers now throw these terms around without having any clue what it really means). From my understanding, you should not be surprised if I told you that "NP-Completeness is one example of Turing-Completeness", it actually has little to do with being equivalent to a Turing machine, that is only one example of 'Completeness'. To determine the Turing Completeness of a language, one must say what class of languages it is Turing Complete with. When the class is NP, we say that the language is NP-Complete, but that is just short hand to say that they are Turing Complete with respect to class NP.

There also seems to be confusion about Turing Equivalence. To say a language is Turing Equivalent by itself is a mistake. Turing equivalent to what?. You have to compare two languages. A Turing Machine is not a language. Two languages are Turing Equivalent if they can be mapped to each other. But those two languages can be very simple languages like a regular language or a context-free language. To say that a language is as powerful as a Turing machine is a mistake. Languages are not machines, there are infinitely many more languages (uncountable) than there are machines (countable).

Turing Completeness and Turing Equivalence are terms applied to languages and actually have very little to do with machines, let alone Turing machines. It seems that people have confused them to mean "Complete as a Turing Machine" and "Equivalent to a Turing Machine". That seems to be where the confusion stems. I'm willing to accept that these terms have become corrupted, that they now have meanings that are foreign to their original mathematical meanings. However, I think the corrupted definition should be reduced to almost a footnote, this is an encyclopedia after all.

With finals coming up I would not have time right away to be bold and make the changes I think need to be made, however I thought I'd like to point people in a direction and hope the article is better when I look at it again during the Winter break.

74.194.27.5 (talk) 06:15, 28 November 2007 (UTC)

I think the above poster's case is a bit overstated, but I do agree that the article needs to be corrected on several points. Here's my 2cents on some specifics in the introductory section alone (where I use "system" in reference to a computational model, whether a programming language or an abstract machine, etc.):
(1) Turing-completeness — A computational system that can compute every Turing-computable function (i.e., the partial recursive functions) is called Turing-complete. Alternatively, such a system is one that can simulate a universal Turing machine.
(2) Turing-equivalence — A Turing-complete system is called Turing equivalent if every function it can compute is also Turing-computable; i.e., they compute the same class of functions. Alternatively, a Turing equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing-equivalent, which adds support to the Church-Turing thesis.)
(3) (Computational) universality — A system is called universal with respect to a class of systems if it can compute every function computable by systems in that class (or can simulate each of those systems). Typically, authors use universality with respect to a Turing-complete class of system. Some authors also distinguish as weakly universal a system (e.g. a cellular automaton) whose universality is achieved only by modifying the standard definition of Turing machine so as to include unbounded input.
(1)-(3) is a summary of how I've found these terms (Turing complete, Turing equivalent and universal) to be commonly used in the literature. It would be great if someone also clarified the connections, and lack thereof, between these usages and the ones couched in terms of set theory. I'm pretty sure they have diverged to the point where the connection is no longer straighforward, if it ever was. --r.e.s. (talk) 15:55, 28 November 2007 (UTC)
I've revised the introductory section in accordance with my (1)-(3) above, and trust that others will make further revisions as appropriate. --r.e.s. (talk) 16:24, 28 November 2007 (UTC)


This page discusses the meaning of Turing completeness and the effects of it, but lacks the actual definition. The only thing said is that a turing-complete system can calculate anything that any computer (a turing-complete system?) can. Even if this is not a strictly circular definition, it still is completely useless on its own.

A famous example of non-Turing complete language is OCL Object_Constraint_Language Here is a good proof. http://projekte.fast.de/Projekte/forsoft/ocl/4_3Turing_Completeness.html

It seems to me the comment on hyphenation rules etc. in the opening paragraph is more useful to article writers than to someone wishing to understand Turing completeness. Should it be removed? 70.194.26.134 11:02, 19 November 2005 (UTC)

I removed the comment from the page. it read: Under traditional hyphenation conventions, the adjective Turing-complete should be hyphenated, but the noun Turing completeness need not be. Yaco 22:27, 9 March 2006 (UTC)

I removed discussions of HTML from this page (sorry, I forgot to login). HTML is simply a descriptive language. When talking turing completeness, we should really be comparing to finite state machines and such things I think. Mrjeff 20:13, 28 Oct 2004 (UTC)

The statement on this page that asserts "Turing-completeness is significant in that every plausible design for a computing device so far advanced (even quantum computers) can be emulated by a universal Turing machine." is, I believe, incorrect.

Assuming that there is actual randomness in the physical world, such as the decay time of a radioactive atom, then a physical computer can use such information to choose, say, whether to output a 0 or a 1 unpredictably. The same program, run repeatedly, gives a varying output. A universal Turing machine, however, given a particular input tape describing an algorithm that terminates with the output of a 0 or a 1, will always produce the same output.

but a universal Turing machine could be programmed to simulate every possible behavior sequence of a nondeterministic machine like that, as long as they're discrete. It'd interlace them, so that even if some of the sequences don't terminate, it'd still simulate any given step of any of the sequences eventually.
Simulating something is not the same as running through all of its possibilities. To simulate a nondeterministic finite automaton like that means, given its start state, that after N steps you are in some state x with the same probability as the thing being simulated. I defy anyone with a Turing Machine to change a state with probability exactly (pi-3) -- you can come as close as you like, but it still isn't exact. Please see "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer" by David Deutsch (e.g. at http://www.qubit.org/oldsite/resource/deutsch85.pdf ) for several examples of things that Turing machines cannot do, but quantum computers theoretically can. While I do not claim that these applications have yet been realized, that isn't the point; the point is that the article claims "Turing completeness is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine." Surely quantum computers are at least plausible. Ruberik 20:47, 5 July 2006 (UTC)

One must understand "computing device" to be a device that instantiates an algorithm in the original article. If the term includes physical computers, then the assertion is not correct.

Again, the simulated systems don't have to be deterministic, they just have to have discrete states. And in fact, even a true analog computer with a continuous range of states can be simulated by a universal Turing machine to any desired accuracy other than "perfect", and therefore it can be simulated accurately enough that humans cannot perceive the difference, let alone use it to "compute" anything. If I remember, Turing spent a good chunk of effort dealing with issues like these in his original paper. -Daniel Cristofani.

jef@jefraskin.com


Does "Turing-complete" really imply that the system is no stronger than a Turing machine? I thought it just meant no weaker.

JC

It means both, but nobody ever bothers to prove the "no stronger than a Turing machine" part, since it's true of every system we've been able to think up.

Moved the following from the article:

"<!-- what the hell does this mean?? -->"


Explanation of some cleanups of 6/1/04.

Buildings are named "in honor of" people; but naming inventions, theorems, etc. for the discoverer is not an "honor", it's standard practice.

A Turing machine's tape is not infinite; it is finite at any given time, but more tape is added whenever the machine is about to run out. It was important to Turing that the machine be physically realizable in principle. If "indefinitely enlargeable" sounds graceless, try to think of something better. "Unlimited" would be okay.

Brainfuck is my favorite language, but it has loops and (unnamed) variables, commands are executed sequentially, and in general it's not nearly as different from normal languages like (say) C as (say) the lambda calculus, or Markov algorithms, or Post systems, or Wang tiles, or Rule 110, or Game of Life, or, well, lots of Turing-complete systems.

Declarative languages can be Turing-complete--Prolog is one example. I tried to clean that paragraph up a bit.

-D. Cristofani.

Why is brainfuck mentioned? Just because it's someone's favorite language? How about mentioning a Turing Machine instead? In brainfucks page it mentions that other than its IO its just a minor variation of P Prime Prime. I think Brainfuck needs to be removed. Its just there for shock value as far as I can tell.

[edit] Criterion for Turing-complete languages

I'm not a computer scientist, so I won't edit the article myself, but I'd argue that any summary of Turing completeness should include a description of the criteria used to determine if a language is Turing-complete. As I understand it, these criteria are:

1) The ability to execute statements sequentially 2) The ability to store integer variables 3) Selection (if statements) 4) Unbounded loops (while statements)

I'd think that most people visiting this page are amateur programmers who have just found out that their favorite langauge is "Turing-complete" and want to know what that means. The above would be closer to what they're looking for.

But it's very incomplete, those criteria just describe imperative programming languages. Turing-completeness is much broader and includes, for example, functional languages, which do not fit into these criteria. Also, Turing-completeness is a mathematical concept, not just a feature of programming languages. --Pepve 22:13, 19 February 2007 (UTC)

I think the context of "Another famous example is regular expressions, as contained in languages such as Perl." is ambiguous as to whether Perl an example of a Turing-complete or of a non Turing-complete language.

[edit] removed 'reliability' as a reason a Turing Machine can't be built.

A Universal Turing Machine doesn't have an OS. If it "crashes" it has in fact halted. Saying it couldn't be built because it might crash makes no sense.

[edit] Turing-completeness of the universe

Changed this:

It is hypothesized by some that the universe is Turing-complete (see philosophical implications in the Church-Turing thesis and digital physics).

To this:

It is hypothesized by some that the universe is computable on a universal Turing machine, which would imply that no computer more powerful than a UTM can be physically built (see philosophical implications in the Church-Turing thesis and digital physics).

Justification:

This is incorrect usage of the term Turing-complete. When we say that X is Turing-complete, we mean that X can do everything a UTM can do, not that a UTM can do everything that X can do. What digital physics proposes is the latter, that physics is exactly computable, that a UTM is universe-complete. Whether the universe is Turing complete is different issue, hinging on whether or not it is possible to perform a finite or infinite number of computations within the lifetime of the universe (thermodynamic lower bounds on power needed for computation) and on whether the universe has finite or infinite state.

[edit] What is Turing-completeness?

The article is surprisingly silent on exactly what features must be possessed (or must be emulatable) by a Turing-complete language. What features are necessary? Speaking in terms of standard programming languages, I would assume that what's necessary is assignment and reading of variables, conditionals, and arbitrary while-style loops. Is that too much or too little?

All it needs to be able to do is emulate a universal Turing machine, or something computationally equivalent. It doesn't matter how it does it, only that it does it. --Robert Merkel 03:51, 7 November 2005 (UTC)
Is this concept so complex that it can only be described by using its name as its definition? That is a poor excuse for an explanation. ("It doesn't matter" won't help anyone but those who already know what it is). Please elaborate in the article what it does. --Blainster 18:13, 12 December 2005 (UTC)
If you want to read about what a universal Turing machine is, read that article, to which there is a link. Trying to fully grasp Turing completeness without understanding the concept of a Turing machine is a pointless exercise. That said, I've added a very brief description of a Turing machine to the article. --Robert Merkel 00:42, 13 December 2005 (UTC)
I've only taken one course in computability, but wouldn't be able to give a really simple definition of Turing complete be a proof of the Church-Turing thesis? 134.117.196.45 16:54, 1 May 2006 (UTC)Jordan
The Church-Turing thesis cannot be proved, as explained in Church–Turing thesis. --Pepve 21:51, 19 February 2007 (UTC)
So a machine is still Turning-equivalent even though it would take the universal turning machine an exponential (or greater) amount of time to emulate.--ANONYMOUS COWARD0xC0DE 06:41, 26 June 2007 (UTC)
Indeed, it's about computability, not about tractability. Pepve 14:26, 28 August 2007 (UTC)

[edit] good non-turing complet language: 3D shaders

There is a section which reads "It is difficult to find examples of non-Turing complete languages,", one nice example of a quite usefull but non-turing complete language would be the shader languages (HLSL, GLSL, CG) used in OpenGL and DirectX, early version of them lacked branching and looping constructs if I remember correctly.

If anybody can confirm this, it should be added to the article as it would be a quite an illustrative example (pardon the pun). --Robert Merkel 23:42, 23 January 2006 (UTC)

Shader models 1.x and 2.0 are indeed not Turing complete, because they lack a generalised iteration capability (they do have some limited looping constructs, but this is effectively unrolled at compile time, so the number of iterations must be constant).

Shader model 3.0, which is used in the latest PC hardware and on Xbox 360, has fully general looping abilities and is Turing complete in the theoretical sense. This rather nicely highlights the difference between theory and practice, though! When people claim a device is Turing complete, what they actually mean is "if this had infinite time and infinite storage, it would be Turing complete". Shader model 3.0 is still extremely limited in register space and program instruction count, so it fails rather badly when put to any real world test.

Note that even shader 1.x can become Turing complete if you allow multiple passes of rendering operations. For instance it is trivial to implement the Game of Life using repeated render-to-texture operations. In this case the input and output textures provide a large amount of storage space, and the repeated render calls fills in for the missing iteration constructs. This is cheating, though, because it is depending on the CPU to issue the render calls!

[edit] thoughtless thought experiment

Does anybody else think the thought experiment about having "unlimited storage" by connecting to the internet is not really a very insightful thought experiment? The only reason it "works" is that it seems to pretend that current trends in the increase of storage space on the internet will last forever, which, if possible, is not really relevant. This is basically the same thing as adding hard-drive space to a computer whenever it needs it to continue with a program. It should at least be pointed out that you can't get around the problem of unlimited storage by pretending that the internet connects you to an unending supply of it...as though the internet connects you to a different Universe. Cesoid 05:11, 28 March 2006 (UTC)

I cannot agree more with you! This 'experiment' is not worth mentioning 82.229.209.33 21:16, 20 April 2006 (UTC)

[edit] Definition

I think the definition of Turing-completeness should be: "A certain computation abstraction (such as a programming language or an automatic machine) is Turing complete if it has the same computational power as a Turing machine." There is no need for the universal machine here. Although it is true that any abstraction that can emulate a Turing machine is at least as powerful as a Turing machine, it is usually easier to show that an algorithmic mapping can be made from a Turing machine to such an abstraction. --Pepve 01:05, 20 February 2007 (UTC)

The same computational power as a Turing machine? Which one? Any Turing machine? But any Turing machine can be emulated by a UTM by definition. Besides emulation of a Turing machine in some other computation abstraction generally involves mapping that machine into that abstraction - mapping the machine's tape, symbols, states, and transition rules into constructs expressed in the abstraction. Besides, without mention of emulation, saying that an abstraction has the same "computational power" as a Turing machine is merely begging the question - what does it mean for one thing to have the same "computational power" as something else? —Preceding unsigned comment added by 60.234.168.92 (talk) 19:52, 17 October 2007 (UTC)

[edit] Procedural programming languages vs. Object-oriented languages

I think that separating between OO and procedural is over simplistic as most languages nowadays are Multi-paradigm programming languages and also bluntly wrong as for example Ada 2005 is any bit as OO as C++ is (with both really being Multi-paradigm).

--Krischik T 07:56, 9 March 2007 (UTC)

[edit] Turing Completeness vs. Spreadsheets

Spreadsheets are simple form of dataflow. In a spreadsheet, you have a two-dimensional array of cells, and each one can be assigned once. If we neglect the 65535 limit for vertical and horizontal cells, we can assign each cell a formula that evaluates previously assigned cells, thus forming a loop corresponding to two nested for loops. The limitation on the number of cells echoes the limits on memory present in all present-day computers. This contradicts the assertion

"Another example is a series of mathematical formulae in a spreadsheet with no cycles. While it is possible to perform many interesting operations in such a system, this fails to be Turing-complete as it is impossible to form loops"

See the article on Dataflow for more on this.

ScaledLizard 11:00, 31 March 2007 (UTC)

This would work if you considered a user autofilling formulas down sets of rows (and/or columns) until it looks like the machine has terminated on an output to be part of a computational process. I think the sticking point here is that this is user intervention, so it doesn't seem like a classical Turing machine where the program and input is set beforehand and then the machine runs automatically. I agree that this is just semantics.
Is a person who knows how to simulate a Turing Machine and has a notebook with lots of paper Turing-complete? I guess so... Tmdean 07:03, 1 April 2007 (UTC)
The user intervention simply consists of filling a range of cells with the formula to compute. The cell number can be used as a loop counter, and for interim values additional cells are used. Filling the cells with the formulas can be accomplished for an arbitrary number of cells with a few mouse clicks. This is not so far away from classical programming and thus does not hinder spreadsheeds from being Turing complete. ScaledLizard 11:09, 13 April 2007 (UTC)

[edit] Babbage's analytical engine really Turing complete?

AFAIK Babbage's engine wasn't Turing complete because it lacked the ability to make decisions based on data.

If it was never built how can we know that it was Turing complete, ie. being able to perform any computational task? Invenio 05:32, 30 April 2007 (UTC)

We can look at Babbage's design and note that it supported loops and conditional branches (see Analytical engine). That's enough to get you Turing completeness, and is, incidentally, precisely "making decisions based on data". --Robert Merkel 06:27, 30 April 2007 (UTC)

[edit] We should merge this with Functional completeness

It's the exact same thing so I don't think there is any room for objection to merge it. However, I'm not sure which name to use. With google Turing completeness wins over Functional completeness but with google scholar Functional completeness wins over Turing completeness. Mack the Turtle 01:24, 3 June 2007 (UTC)

I object though, turing completeness deals with automata, functional completeness deals with sets of functions. Could you explain why they are the 'exact same thing'? Pepve 14:39, 28 August 2007 (UTC)
I agree with Mack, they really are the exact same thing. Mike92591 05:16, 2 December 2007 (UTC)

Merging would be a big mistake — Turing-completeness is definitely not the same as "functional completeness". --r.e.s. 05:32, 2 December 2007 (UTC)

Mike92591, very fine that you agree with Mack, but don't you think the same question I posed to Mack applies to you? It doesn't seem too convincing to agree with someone without addressing the rather substantial criticism. -- Pepve 17:15, 2 December 2007 (UTC)

[edit] "Being equivalent ... means being able to perform any computational task — though it does not mean being able to perform such tasks efficiently, quickly, or easily."

I find this sentance a little unclear. It seems to suggest that a requirement of a turing complete language is the fact that it in not efficient, quick or easy. —Preceding unsigned comment added by 202.10.86.59 (talk) 15:13, 20 October 2007 (UTC)

[edit] Turing-powerful

I believe Turing-powerful is a synonym of Turing-complete. There's currently no mention of the phrase Turing-powerful on the wiki. Egriffin (talk) 15:09, 6 December 2007 (UTC)

I've seen that expression used on webpages (maybe by people unaware of the more-common term?), but not in published literature. Maybe it ought to be mentioned anyway, but it would be best to find published sources if there any. Do you know of any? --r.e.s. (talk) 00:03, 7 December 2007 (UTC)
I just searched arxiv.org and found one mention in this paper [1] --Egriffin (talk) 00:21, 7 December 2007 (UTC)
Indeed, I should have looked more closely at what googling turns up (quite a lot of instances in published articles). I've added the term as a synonym of Turing-complete, and a redirect of "Turing-powerful" to this article.--r.e.s. (talk) 01:02, 7 December 2007 (UTC)