Talk:Turing completeness

Computer science Start‑class Top‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

Top

This article has been rated as Top-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

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)[reply]

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:

""

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.

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)[reply]

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.

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.

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.

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)[reply]

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)[reply]

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)[reply]

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[reply]

The Church-Turing thesis cannot be proved, as explained in Church–Turing thesis. --Pepve 21:51, 19 February 2007 (UTC)[reply]

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)[reply]

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)[reply]

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!

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

We should merge this with Functional completeness

It's the exact samething 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)[reply]