Talk:Turing completeness/Archive 1

Archive 1

Untitled

I suggest that people look at the articles for Turing Reducibility 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

--- Better examples of modern sub-recursive (i.e., terminating) languages are those intended to be used as logics. Coq is probably the most popular and famous of these (but it certainly also includes Martin-Lof's Type Theory, Agda, Matita, etc.). In such cases, it is absolutely critical that programs be total in order to maintain soundness of the logic. Epigram (currently mentioned) is also a fine example, but Coq is much more mature and has orders of magnitude more users. —Preceding unsigned comment added by 99.75.50.148 (talk) 03:13, 9 March 2010 (UTC)

---

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?? -->"

---

needs proof of equvilance mabey for lambda calculus ?

---

— Preceding unsigned comment added by Turingproofs (talk • contribs) 16:23, 8 December 2011 (UTC)

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)

Rather, what's needed is to separate the 'folk' concept of Turing-completeness in terms of real world programming languages, and the ability to compute all recursive sets (given an absence of resource constraints). But that needs to be done by the Theoretical Comp-Sci and (practical) Comp-Sci communities, rather than in a talk page on a Wikipedia article. Chalisque (talk) 22:26, 16 January 2017 (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.

Criterion for Turing-complete languages and infinite tape

In fact, no realization of programming languages is truly Turing-complete, as completeness relies on the possibility to emulate an infinite tape. When we state that a programming language is TC, we implicitly assume that there is sufficient memory available. Hence, the statement "C is arguably non-Turing-complete as the size of a pointer is required to be finite, hence restricting the available memory." applies to all the other examples. In particular, I don't see any reason why the same argument should not be applied to C++, Pascal or even for LISP implementations. I suggest to precise this before the list of "TC programming languages" and then remove the phrase about C. 81.57.76.47 (talk) 07:16, 20 October 2010 (UTC)

The tape does not need to be actually infinite, just able to be extended whenever it runs out of room. It is standard terminology to talk about C, C__, etc. being Turing complete even though (for example) their integer data type is really finite in implementations. If there was an issue in the article, we would need to explain why C is a Turing complete language, rather than remove it. — Carl (CBM · talk) 11:05, 20 October 2010 (UTC)

I believe that C is not Turing complete. It's because size of pointer is finite. And it's not just the realization - it is defined by the language(Other languages may not be that limited, and their limited memory implementations are not part of the language itself) . Maybe someone more knowledgeable can prove me wrong and point to some detailed explanation/proof. Until then I think C should be removed (maybe C++ too). Striepan (talk) 11:45, 9 April 2014 (UTC)

Presumably by "size of pointer is finite" you mean "has pointers"; no programming language in the real world that has pointers has infinite-sized, obviously. As such, if C isn't Turing complete, neither are any other languages with pointers, including, but not limited to, C++, Objective-C, and PL/I. Guy Harris (talk) 17:11, 9 April 2014 (UTC)

Yes, that was my point. But I don't know if these languages have other means of simulating unbounded tape. Striepan (talk) 21:48, 9 April 2014 (UTC)

What do reliable sources have to say regarding this question? (After all this is no place for publishing original claims, but FWIW I'm inclined to think that if no real language can be TC by your definition, then that definition of TC might be lacking nuance.) Cesiumfrog (talk) 07:13, 10 April 2014 (UTC)

Isn't that a formal thing? As in something that should be proved. I haven't seen any proof and I doubt that "no real language can be TC". I'm just suggesting that C isn't. Besides, there are other models of computation that are sufficient for any useful computer programming(e.g. Finite-state_machine, Linear_bounded_automaton). Are there any reliable sources on this? And are they reliable if they don't provide such proof? Isn't it lousy, throwing around that this and that is TC when we are dealing with pretty big and formal theory? Because you can say "it's got loops n' shit" and it's enough to program in the real world :) Btw. my definition? TC definition is pretty clearly stated in the article. Striepan (talk) 21:02, 27 April 2014 (UTC)

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)

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)

Completely agree here. Every "explanation" seems to go back to that circular logic. I have put in a concept tag until somebody fixes this for the layperson to understand. SineSwiper (talk) 12:01, 11 July 2009 (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)

It is worth remembering the history of the concept, from a time before programmable electromechanical computers were invented, and where a 'computer' was a mathematician performing computations. The central concept is that of an Effective_method, which is explained concisely, and gives the starting point for what an 'algorithm' is. From there, Recursive_set is your next port of call. My take for a definition is as follows:

Something is Turing complete if and only if it can compute the answers to (yes/no) questions of the form 'is x in S' for every recursive subset $S\subseteq \mathbb {N}$ and for every $x\in \mathbb {N}$.

It is a concept from the foundations of mathematics, back in the early 20th Century, when people like Hilbert, Russell, Godel and Turing were worrying essentially about the reliability of mathematics. Mid-to-late 19th century we had the beginnings of the axiomatisation of arithmetic (Peano, Dedekind and friends, see Peano_axioms) and the beginnings of set theory with Georg_Cantor. Then Russell came along with Russell's_paradox and the world's mathematicians had serious cause to worry. I doubt either Church or Turing had in mind quite the 'magic box with screen, keyboard and flashing lights' we know as a 'computer' when they produced the results they did. Things like Turing completeness come from the mathematics behind modern computing. Chalisque (talk) 22:17, 16 January 2017 (UTC)

I second (or third or fourth) the notion that this article does not define in clear terms what Turing completeness is. We need a systems expert to at least attempt a definition understandable by a typical undergraduate student. —Preceding unsigned comment added by Rboone2020 (talk • contribs) 03:00, 30 July 2008 (UTC)

Which part of the following quotation is unclear to you? "A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a universal Turing machine."

An explanation that is clear only to people who already understand the concept, however technically correct it may be, is not a useful explanation. If the only explanation that can be given is a circular one, then the two pages should be merged. —Preceding unsigned comment added by 66.66.6.25 (talk) 20:50, 17 February 2010 (UTC)

A Turing-computable function is defined to be a function computable by some Turing machine. This definition does not involve the concept of Turing completeness, so there is no circularity. It happens that these functions can also be computed by any one of many other computational systems besides Turing machines — any computational system with this capability is called Turing-complete.
— r.e.s. (talk) 17:02, 19 February 2010 (UTC)

I suggest that if you're unclear about the meaning of "Turing-computable function", or "universal Turing machine", then your comments should go to the Talk pages of those articles. I doubt that there is a clearer definition of Turing completeness than the one just quoted.
--r.e.s. (talk) 03:15, 30 July 2008 (UTC)

Wikipedia articles should describe "Turing completeness" in a lay accessible way--- it's not the most difficult of concepts. A "universal turing machine" is just "a computer with arbitrarily large memory". A "turing computable function" is any function which represents the result of a computer program acting on integers. A clear definition just de-jargonizes what you said.Likebox (talk) 17:42, 19 February 2010 (UTC)

You essentially removed the correct definitions without discussing the issues here. It might be more useful to everyone if you were to simply add a section that contains what you regard as a more "lay accessible" explanation, leaving the correct definitions intact. — r.e.s. (talk) 18:45, 19 February 2010 (UTC)

What you call the "correct definitions" is just jargon for the same thing. Please do not remove such a large amount of new text without consensus, especially since it seems that you are the only one that opposes it.Likebox (talk) 18:51, 19 February 2010 (UTC)

It is you yourself who removed a large amount of text without discusssion. Please do not again make such a change without discussion here. — r.e.s. (talk) 18:55, 19 February 2010 (UTC)

If you look at the size of the page, you can see that the article was expanded by my additions. I did not delete anything--- I rephrased the lead. What don't you like?

My issue with the current lead is that the phrase "turing machine" and "turing computable function" are used without the explanation that these are synonymous in this case with "computer" and "subroutine taking integer and returning integer". These terms are trivial for a modern person to understand, and hiding their meaning by exclusively using the jargon of Turing machines is a little old fasioned.Likebox (talk) 22:38, 19 February 2010 (UTC)

No, those terms are not synonymous. These are examples of the inaccuracy and imprecision I was talking about. Turing completeness describes some, but not all, abstract machines (but no finite-resource computer), and a Turing computable function is not a subroutine (it's a mathematical function, a mapping from one set to another). It's definitely not "old fashioned" to use terminology that's accurate, precise, and standard.
— r.e.s. (talk) 14:48, 20 February 2010 (UTC)

(deindent) To be clear--- I was responding to the tags, which requested that the lead be made more accessible. The text I provided was simpler, and said exactly the same thing. I am annoyed that you call it "imprecise". What exactly is imprecise?Likebox (talk) 22:40, 19 February 2010 (UTC)

No, your replacement text does not say "exactly the same thing". One example is that in your version, a TC system "can produce the result of any calculation". That introduces the nebulous phrase "any computation", and appears to hide a tacit assumption of the Church-Turing thesis. (A correct definition of TC is independent of this thesis, and should actually help to explain the thesis.) Another example is your statement that "even the simplest computer can be used to simulate the most complicated one". This is definitely not true — first of all, it over-generalises the TC concept (which concerns mathematical functions), and secondly it wrongly implies that all computers (even ones with finite resources) are TC. What you call "relatively trivial finite-memory issues" may be trivial when placed in the proper context, in which they are discussed after first giving a correct definition of TC. The mathematical nature of the TC concept should be preserved in any case.
— r.e.s. (talk) 14:48, 20 February 2010 (UTC)

I know the definition of Turing machine and computable function, and I don't know anyone who would get misled by the statements that I made. A Turing machine is synonymous with a computer with infinite RAM. That's it. There is no reason not to state this fact. The memory issues are trivial--- everyone understands what "buying more RAM" is, and everyone understands the idealization "buy as much RAM as required to finish the computation". The chance for misunderstanding is zero.

A Turing computable function is a function that can be written as a subrouting which takes an integer and returns an integer, on a machine with potentially infinite memory. That's it. There's no more and no less to the definition. I spoke without distinguishing the procedure from the function, and there is no reason not to do so. There is no chance of confusion

The text I wrote was careful to state the finite memory business so that readers could not get confused on the (trivial) points you bring up. You are right that I was assuming Church Turing thesis, but the lead is supposed to assume whatever is necessary to make the article comprehensible and accessible. There is no reason not to put a definition in formal language (the way you like) in the first section, and to keep the lead informal.

Your preferred text, however, is written like a robot--- like someone who has no understanding beyond reading a definition in a textbook. This is a bad way to present a technical concept, and shows lack of understanding of the actual concept. It is better to explain the concept in simple words.Likebox (talk) 17:07, 20 February 2010 (UTC)

Less than 15 hours after my previous comment, you reverted the article (again), saying "No discussion, so restore". I am unable to guarantee even daily responses, and I won't engage in an "editing war" with you, even though numerous statements in your latest comment above are misleading oversimplifications. Due to various circumstances this may be my last effort here, so, for the record ... I strongly recommend the following alternatives:

(1) simply move the formal definitions to a subsection with that title (contrary to your notions, a formal definition certainly does not reflect a lack of understanding);

(2) have a simplified introduction without oversimplifying or pretending that an informal definition is the same as a formal one (include words to the effect that it's "informally speaking", "loosely speaking", etc., and make it refer to the more-formal section);

(3) maybe include an informal subsection.

For comparison, take a look at the Turing machine article — although it's not perfect, it is informal where appropriate, without sacrificing the formal definitions altogether. In my opinion, your present version of the article has performed editorial surgery so drastic that it has killed the patient.
— r.e.s. (talk) 14:48, 22 February 2010 (UTC)

Would you like me to copy and paste the formal definition to a first section, entitled "formal definition"? I will do that now, tell me how you like it. I am sorry for acting too quickly, I just was involved in a pile of other things, and was checking WP frequently.Likebox (talk) 14:51, 22 February 2010 (UTC)

(deindent)I did that. This is the sentence that made me cringe when I read it:

The term weakly universal is sometimes used to distinguish 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.

Turing machines have "unbounded input". What you meant, I think, is infinite input. That is indeed a different type of machine--- an oracle machine. Could you clarify or fix this? I fixed it in the new lead in informal language.Likebox (talk) 14:58, 22 February 2010 (UTC)

Turing machines in the usual sense also have "infinite" input: every cell of the infinite input tape is either a 0 or a 1, or either blank or marked. Some texts say the tape is "finite but indefinitely extensible" but I think it's just as common in contemporary texts to assume the tape is infinite. Surely what is meant above is that the set of squares that are not blank is bounded. — Carl (CBM · talk) 15:17, 22 February 2010 (UTC)

I saw the changes Likebox made a while back, and they do have the problem of conflating "computers" with "computable functions". The two are not the same; a computer is a finite device that only has finitely many possible states, and a Turing machine is not a "computer" in the usual sense of the word. In particular, "the most primitive computer" would include my pocket calculator, which is certainly not Turing complete.

However, there are really two different notions of what "Turing complete" means. The first refers to theoretical models of computation which are equivalent to Turing machines. This is the definition R.e.s. is talking about. The second refers to programming languages that are equivalent in computing power to general-purpose languages such as C. These languages are "Turing complete" in the first sense only if they are not run on actual computers, but are "run" on theoretical models instead. — Carl (CBM · talk) 15:17, 22 February 2010 (UTC)

What you are saying is true, but I believe the distinction is made too harshly. Modern computers have enough RAM/disk space etc that the idealization of infinite memory is not inappropriate. It's like describing a frictionless plane by an air-hockey table--- it's not perfect, but close enough that nobody would get confused.

But more substantively--- the input to a Turing machine is required to be finite, meaning that at time 0 only finitely many of the input slots are set to 1, and the rest are 0. This is what "unbounded input" means. On the other hand, if you set infinitely many spots to 1, you can get an oracle machine, by, for instance, encoding the halting oracle at the odd positions.Likebox (talk) 15:29, 22 February 2010 (UTC)

Right; one identifies the input with the set of squares marked 1, so having an "infinite" input is the same as having an "unbounded" input. If one identifies the input with the set of all squares, which forces the input to be "unbounded", then the input has to be "infinite" as well. — Carl (CBM · talk) 15:33, 22 February 2010 (UTC)

Got it. That's a little confusing--- it should be made clear that the words "unbounded input" means infinitely many bits sent in. That's not what it usually means to people.Likebox (talk) 18:55, 22 February 2010 (UTC)

Regardless of all the dissent I think everyone can agree that it is meaningless to say, "Turing completeness is defined by what a Turing machine can do." The number one rule of defining a term is to not use the term in the definition. That isn't a definition that's an obfuscation and becomes dangerously close to being recursive, "What's Turing completeness? It's what a Turing machine can do. And what can a Turing machine do? Anything defined by the rules of Turing completeness. What's Turing completeness? It's what a Turing machine..." ad infinitum.

So, I would greatly appreciate someone with formal knowledge of this topic to succinctly define exactly what Turing completeness is without using the word "Turing" in the definition. —Preceding unsigned comment added by 184.91.37.207 (talk) 09:32, 3 August 2010 (UTC)

Here's an analogy, intended to be playful, that might help a complete newbie to see why your request is misguided. We could say that any item is Walmart-obtainable if it can be obtained at a Walmart store, and we could say that any other store is Walmart-complete if it sells every Walmart-obtainable item; likewise, we could say that any other store is Walmart-equivalent if it sells exactly the same collection of items as do Walmarts:

item                     <---> function
obtain an item           <---> compute a function
Walmart store            <---> Turing machine
other stores             <---> other computational systems
Walmart-obtainable       <---> Turing-computable
Walmart-complete store   <---> Turing-complete computational system
Walmart-equivalent store <---> Turing-equivalent computational system

Now suppose that certain other stores (say Xmart, Ymart, ...) are Walmart-equivalent (e.g., Xmart and Walmarts sell exactly the same collection of items). Then it's true that we could define Walmart-completeness without referring to Walmart, e.g., by first defining Xmart-obtainable and Xmart-completeness in terms of Xmart, and then defining Walmart-completeness in those terms -- but this would merely shift to Xmart the "problem" you were mistakenly perceiving. However, it should now be clear that there's nothing at all wrong (and everything right) about referring to Walmart stores in order to define Walmart-completeness (and likewise referring to Turing machines to define Turing-completeness). Does this help?
— r.e.s. (talk) 15:09, 21 October 2010 (UTC)

The first I ever saw the phrase "Turing Complete" was on usenet where it was bantered about endlessly as if some self defining authority. I couldn't find a sensible usage criteria for it. I quickly because convinced that it was a term that Turing himself would never have expected to have taken flight. It a term that lives within self definition, and an unbelievable amount of energy is spent trying to get a handle on this thing. As a computer scientist I've looked carefully into this concept for decades and I still come up empty handed, and when I do find a source that starts to shed some light on what it was intended on being, I only discover it to be hotly contested. From my point of view it is a term without meaning, without importance, and a term with the sole goal of manifesting confusion. I hear someone mention that something is or isn't "Turing Complete", and they're immediately labeled by me as someone to divert my attention from.Tgm1024 (talk) 17:10, 29 May 2014 (UTC)

good non-turing complete 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! — Preceding unsigned comment added by 131.107.0.106 (talk)

If "what they actually mean is 'if this had infinite time and infinite storage, it would be Turing complete'", then why don't they actually say so? There's a word for that: LBA-complete. --Damian Yerrick (talk | stalk) 16:37, 30 May 2009 (UTC)

Another example of a non-turning complete language in wide use would be G-code I think, it is used to control CNC machines. There might be similar languages for robotics. A common day example would probably be the mail filtering in your email client. I think the C example should be removed or rewritten, as basically all actual languages fall into the "limited memory" category, which by the way shouldn't even be that much of a limitation, as nothing stops you from attaching a harddrive with infinite memory. -- Grumbel (talk) 07:31, 9 September 2010 (UTC)

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)

Unacceptable Definition

The current definition is useless. You can't define something by using the word you are defining in the definition. The definition needs to be completely re-written. Why does no one get this? It's like if I defined "definition" as: A definition is the definition of a word. Get it? You cannot use the word you are describing in its own definition. I think this topic should be taken offline until it is corrected. These kinds of horrible answers just give people that hate Wiki's, because they argue Wiki's don't provide trustworthy information, more ammunition. And in this case they would be right.

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)

I think the "computational power" of a Turing machine is pretty well-defined: It computes all computable functions. So if you prove that your model/machine/whatever is capable of that, you prove it has the same computational power as a Turing machine -- the largest computational power there is. Which, by the way, is often nicely done by proving you can transform any instance of your model into a Turing machine (yes, "a" Turing machine. Any one. "there has to exist a Turing machine that is 'equivalent' to this model"). Which is what Pepve suggested. 92.60.245.178 (talk) 09:05, 10 October 2012 (UTC)

Using the term you are defining in the definition is a horrible idea. "What's catflapping? It's what a catflap does." Meaningless. —Preceding unsigned comment added by 184.91.37.207 (talk) 09:37, 3 August 2010 (UTC)

This definition does not use the term it is defining. The Turing Machine is a distinct concept from Turing Completeness. If the reader doesn't understand what a Turing Machine is, they should read the definition of a Turing Machine. — Preceding unsigned comment added by 87.79.90.204 (talk) 06:57, 4 April 2014 (UTC)

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)

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)

The number of cells that can be used in a spreadsheet is not bounded, as you do not have to store the formula for every cell. You can have sparse representations that say, "this formula fills that range", or "this formula fills my entire document". Cell values can be computed when needed, so they need not be stored either. As the number of cells in a spreadsheet is not bounded, you can have unbounded loops. Limits on time and memory are always present in physical implementations of computing machinery, but they are usually ignored, as the same limits are present in a human mind. ScaledLizard (talk) 05:05, 20 April 2011 (UTC)

So you can fill an "infinite" (i.e. spreadsheet-sized) range of cells in a single operation, using the same memory for all the formulas? OK, that should be enough for Turing-completeness. Ben Standeven (talk) 23:42, 17 April 2013 (UTC)

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)

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)

While I think "functional completeness" and "Turing completeness" are very closely related things, the discussion here and at Talk:Functional completeness has convinced me they are not the "exact same thing".

They are closely related -- if I had large enough quantities of some set of physical hardware that implements a functionally complete set of functions, plus some way to cascade the output of one function to the input of some other, then I can build a Turing machine -- right?

And vice versa -- if I have large enough quantities of some physical hardware that is sufficient to build a Turing machine, then that set of hardware components is more than sufficient to build hardware that implements a functionally complete set of functions -- right?

Is this relationship something that needs to be more WP:OBVIOUS in both articles?

Both the "functional completeness" and "Turing completeness" articles talk about abstract mathematical properties. Is there an article that lists the kinds of physical hardware ("set of physical hardware") that has been used to build Turing machines? --68.0.124.33 (talk) 01:08, 15 April 2009 (UTC)

The is no Turing complete physical hardware as Turing completeness demands unlimited memory which does not exist in real live. You only got hardware which would be Turing complete if memory was unlimited. But That goes for everything that claims Turing completeness. --Krischik ^T 07:30, 15 April 2009 (UTC)

"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)

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)

XPath is a is not Turing-complete language but XQuery is according to How XQuery extends XPath IBM article is that true? I am just a simple developer and lacks the academic theory to confirm it. But if it is true I think it should be mentioned since they are more common ( in the real world outside of the campus) then Brainfuck and Haskel.

SQL is no longer non-Turing Complete

The article says that SQL requires proprietary extensions to be Turing-complete. This is not true as the ISO SQL standard has included recursive queries for many years now. Also, SQL has had standard Procedure definitions with variables, open loops and conditionals for even longer, so there really is no basis for this urban myth.

68.39.161.88 (talk) 15:51, 14 August 2010 (UTC)

examples

The intro says that conditional flow control (if .. then goto) plus variables (overwrite x with value of y) is sufficient for turing completeness, could someone flesh out this example (how exactly one would emulate a turing machine using a minimal language such as that)? A different such example would also be good too (eg., how exactly one would emulate a turing machine using lambda calculus?). And the reverse, how exactly would a turing machine simulate a basic imperative programming language interpreter? Cesiumfrog (talk) 03:56, 7 January 2011 (UTC)

Removing mention to "David Turner" languages

This statement appears too vague and non-notable:

"Languages based on total functions that can work on streams that are in potential, but not formally, infinite are currently being investigated by researchers such as David Turner. This would enable Turing-incomplete languages to be used even for tasks such as systems programming."

Hence, I'm removing it. —Preceding unsigned comment added by 131.114.88.220 (talk) 15:14, 4 March 2011 (UTC)

The need for an explicit HALT state

Since the question Turing (and Church but not as formally) asked was will a UTM ever reach the HALT state implies there must be one and thus a machine that does not have an explicit HALT state (it is possible to relabel ACCEPT and HALT to accomplish the same thing).... For example JavaScript is *NOT* (as it stands [you can simulate a Turing Completeness but JS it self is not) Turing Complete because it has no explicit HALT ("end-of-script" doesn't count because it is undecidable if it receable [the halting problem is "partially decidable" in that you can always say if it will halt in a finite amount of time if it does in fact do so but you can not say that it will never halt in a finite amount of time).... for all these reasons I am adding the requirement to last sentence of the first paragraph —Preceding unsigned comment added by 67.85.81.211 (talk) 23:07, 18 May 2011 (UTC)

Relivence of HALT'les langs

I originally read this article since it was mentioned as a reference in http://www.php-security.org/downloads/bco.pdf. The author of the paper (slightly incorrectly) used the orginial statement in the second paragraph of the opening section to incorrectly assume that a TC VM In JS was possible... it is not possible *directly* in JS to be TC but since JS is a stateful lang that allows an arbitrary number of stacks then according to the proof for problem 3.22 in Sipher (Intro. to the Theory of Computation) we are asked to show that a PDA with 2 stacks is in fact equivalent to a single tape UTM... more generally a PDA with k stacks is equal to a UTM of k-1 tapes (and it is well known that adding tapes does not increase the types of problems that can be solved it just increases efficiency).... put an other way JS is not TC but it is possible to write a simulation in it that is TC.... so the relevance is to show that there is no non-priopritory (flash, silverlight, etc.) front-end web language that is TC. (for very large and complex sites or front-end frameworks this is a serious issue for example it prevents AJAX from working in arbitrary concurrency) —Preceding unsigned comment added by Aryeh M. Friedman (talk • contribs) 01:46, 19 May 2011 (UTC)

Isn't the definition of "Turing complete" simply "able to emulate a Turing machine"? So if a programming language can emulate a Turing machine (or can be used to make an interpreter for another language that can), then it is Turing complete. If A can simulate B and B is TC then A is TC; "(in)directly TC" is tautological/oxymoronic. It doesn't matter whether the language has a native Halt command, it only matters whether it can simulate a Halt command (which is pretty trivial in practice, an infinite empty loop suffices), just like it doesn't literally need to have a native instruction for advancing the tape left or right. Or am I missing something? Cesiumfrog (talk) 06:15, 19 May 2011 (UTC)

Your correct that in theory the ability to simulate a TC lang is sufficient it is a question is semantics (I do not consider TC because TC'ness is a non-trivial special case). You are incorrect though that a

while(true)

  ;

is sufficient simulate a HALT. In a non-concurrent application you can use this trick but since it locks the CPU (sorry for mixing models) it makes multi-tasking impossible thus a busy wait != HALT.... here is how I did it in JS:

try {

  runVM();

} catch(VMHaltException e) {

  ....

}

No - you misunderstand. A "while(1);" statement isn't enough to be a HALT statement in the actual computer - but it IS enough to emulate a HALT statement in an emulated Turing Engine. Then, because you can emulate a Turing Engine without a HALT instruction in the native machine - it is not necessary for a computer to have a HALT instruction in order to be Turing Complete (presuming it's architecture permits one to write that Turing Engine simulator without multitasking - which is a pretty safe assumption because Turing Engines don't have any specific parallelism in them - they have to emulate parallelism if you need it). SteveBaker (talk) 14:08, 9 December 2011 (UTC)

Don't need conditional jump.

The article says "This requires, at a minimum, conditional branching (an "if" and "goto" statement) and the ability to change arbitrary memory locations (formality requires an explicit HALT state)." - and also that a machine is turing complete if it can simulate a turing complete machine. Note also that One instruction set computer says that a computer that is capable of executing just one instruction (SUBLEQ - Subtract and jump if less than or equal to zero) is turing complete.

So - if a machine without a conditional branch instruction were to be able to simulate a SUBLEQ machine then it too would be turing complete.

Now, consider this little C program. It is a simulator of a SUBLEQ machine:

 // Initialization:
 typedef unsigned char byte ;
 int lut [ 256 ] =
    {
      1, 1, 1, 1, 1, 1, 1, ....  // 128 ones.
      0, 0, 0, 0, 0, 0, 0, ....  // 128 zeroes.
    } ;
 byte mem [...whatever...] = { ...whatever... } ;  // The initial state of memory in the SUBLEQ machine
 int PC = 0 ; // The SUBLEQ machine's program counter.

 // Runtime:
 while ( 1 )
 {
   // Read instruction operands from the program counter location.
   int a = mem[PC++] ;
   int b = mem[PC++] ;
   int c = mem[PC++] ;
   // Perform subtraction:
   mem[b] -= mem[a] ;
   // Use lookup table to extract sign of mem[b] so that:
   // c is multiplied by 1 and added to the program counter if mem[b]<=0
   // c is multiplied by 0 and added to the program counter if mem[b]>0.
   PC += lut[mem[b]+128] * c ;
 }

(The lookup table 'lut' is pre-initialized with '1' for negative numbers and '0' for positive ones. the SUBLEQ instruction uses a relative jump - jumping forwards by 'c' bytes if (mem[b]<=0)).

This code simulates a turing-complete SUBLEQ computer (which has conditional jumps) - yet the interpreter uses no conditional instructions whatever and could thus be run on a machine without a conditional jump instruction. Moreover, if the underlying hardware is able to wrap its program counter from the maximum value back to zero, then we don't even need an unconditional jump and the only operations we need are: signed-memory-lookup, subtract and multiply by a one-bit number.

Ergo, it is possible to build a turing complete computer without a conditional jump - so our article is incorrect.

Worse still, that means that the Harvard Mark I and the Z3 (computer) (both of which could loop - but not conditionally) were in fact Turing complete.

Sadly, although this is obviously true - it is WP:OR, so I can't write about it. SteveBaker (talk) 16:55, 30 September 2011 (UTC)

I would say that the ability to directly change the program counter qualifies as a conditional jump. The point is that you have the ability to control, based on logic in the program, which code will be executed next, and change to remote parts of code when desired. In any case, any Turing complete language will be able to simulate SUBLEQ, and so the language will at least be able to simulate a conditional jump.

The deeper problem is that "Turing completeness" as described in this article is not really a formal concept. Worse, the article mixes several types of languages (for example both programming "languages" and regular "languages" are described in the same section "Non-Turing-complete languages"). I have completely given up on making the article clear, because I don't think there are any sources that describe it. — Carl (CBM · talk) 20:10, 30 September 2011 (UTC)

You misunderstand. Of course, the ability to write to the program counter would constitute a conditional jump. What my example (above) shows is that the program (as I wrote it) contains NO conditional jumps whatever, and no writing to the program counter (the variable 'PC' is just a variable) - and so would run on a machine without those features. However, the program above is correctly emulating a 'SUBLEQ' computer which does have conditional jumps. So, you can take your computer that doesn't have conditional jumps - implement my little C program on it, then load up SUBLEQ programs that do contain conditional jumps and they'll run perfectly well - making the combination of non-Turing-complete hardware plus conditional-jump-free software able to behave exactly like a fully-fledged turing-complete machine. Ergo, the definition of "turing complete" should not require conditional-jumps because I have devised a way to make an undeniably turing-complete machine using no-conditional-jump hardware.

I do agree that the concept of "turing complete" is a little fuzzy around the edges - but we do go on to deny the Harvard Mark I the title of "First computer" because of that lack. The deal is that the Church–Turing thesis says that anything that can emulate a turing machine (given enough memory and time) is equivalent to any other turing machine - and any one of them can emulate any other of them. That's profound. It says that if there was enough time and memory that you could run Quake on a Babbage Analytical Engine. However, that gold standard is currently being denied to the Harvard Mark I because of a lack of conditional jumps - when it could in fact easily be programmed to emulate a Babbage engine, which in turn could then run Quake. The threshold of capability between being able to emulate any other computer whatever - and not being able to - is kinda critical. SteveBaker (talk) 20:43, 30 September 2011 (UTC)

The article probably needs to be worded more clearly, but I thought the point was just to provide some simple minimalist examples that would be sufficient for Turing completeness. For example, if+goto+variables is sufficient, and therefore one can see that most common programming languages and most common machine code architectures are obviously sufficient. But it should also be extremely obvious that none of those are necessary. For example, purely functional (rather than proceedural) languages do not have variables nor flow control and yet are commonly still Turing Complete. This confusion keeps cropping up (an example is the requirement of a halt statement, which is false but keeps getting reinserted anyway), so that bit needs to be rewritten using multiple examples of minimal sets sufficient for TC (eg. what is one minimal TC pure-functional requirement?)? Cesiumfrog (talk) 22:49, 30 September 2011 (UTC)

No, it's more than just wording. We deny the Harvard Mk I the honor of being "turing complete" because it lacked conditional jumps. However, by running the program I give (above) - which requires only a single unconditional jump - it could emulate a SUBLEQ machine. Since SUBLEQ is turing-complete, so is the Harvard Mk I. It's not just a matter of wording - we're making statements that are utterly untrue on the basis of that wording. The problem is that we can probably find reliable sources that (incorrectly) state that the Mk I was not turing complete - and I've yet to see one that said that it was. Hence, this argument (although obviously true) is WP:OR and disallowed - which is really annoying. SteveBaker (talk) 14:02, 9 December 2011 (UTC)

I would think that creating an interpretor for your program that uses a program counter variable would in fact count as implimenting a virtual machine which does have a program counter (your variable PC). Your computer does after all have a program counter so if you are in effect only emulating a virtual machine with a program counter that you do change this does not disprove the need for the counter/jumps. So I think that this article remains correct in stating that jumps are required? It does seem that there needs to at least be a way to re-route your flow on command. Unless it is possible to use a circular buffer of memory that loops? (and simple insert into it) 80.7.27.189 (talk) 22:49, 27 February 2013 (UTC)

'A Simple Multi-Processor Computer Based on Subleq' by Mazonka and Kolodin seems to address this matter, I'm not an expert but just my 2 cents. Last time I checked this was still in draft stage(2011) though. — Preceding unsigned comment added by 183.78.207.48 (talk) 15:08, 4 May 2015 (UTC)

Minor[Lede] Problem

Hi all. OK, I'm reading this late at night and tired, but the main header might be accurate, but it doesn't really break down what Turing Complete means to the non-engineer.

Can someone please come up with an analogy, or a visual picture, or some way of bringing this into the real world for the other 90% of us?

Thanks Billyshiverstick (talk) 03:38, 29 July 2012 (UTC)

Turing complete just means able to simulate a Turing machine.

It is important because it is believed that anything Turing-complete is able to do everything that any classical computer could ever do. Cesiumfrog (talk) 07:20, 29 July 2012 (UTC)

Single-Taped

Please include a definition of "single-taped" as it is difficult to find and this is needed to help make the article understandable. Thanks. - KitchM (talk) 18:55, 7 July 2013 (UTC)

Weakly complete

I removed the sentence "A machine which is universal except for having access to some Turing oracle is called weakly universal" as it seems incorrect and is hard to parse. The literature I have defines "weakly complete" as having access to a starting tape which may be infinite but is ultimately periodic: see for example Lagarias, Jeffrey C., ed. (2010). The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. p. 20. ISBN 978-0-8218-4940-8. Zbl 1253.11003. Deltahedron (talk) 06:55, 28 June 2014 (UTC)

Turing completeness of extant machines

The discussion of the completeness or otherwise of machines actually built seems flawed. We have to go by what reliable sources say, of course, but no single instance of a physically built machine can have anything but a finite number of states. It is reasonable to ask whether an idealised Z3 machine with access to an infinite memory tape is Turing-complete, but the answer for the Z3 machine as built has to be "no". So what does the source quoted say? The article currently says "The first machine capable, in principle, of being Turing-complete was the program-controlled Z3" but that cannot be correctg as I have observed. Indeed, the reference cited says "Zuse's Z3 is therefore, at least in principle, as universal as today's computers which have a bounded addressing space" and almost immediately after "Nobody has ever built a universal computer"" [italics in the original] [2].

Since the paragraph in question is otherwise unsupported, I proposed to remove it for discussion here. Deltahedron (talk) 15:46, 28 June 2014 (UTC)

Turing Incomplete Languages to prevent abuse

I came here to get a somewhat formal definition of Turing completeness, to figure out why Bitcoin script is considered safe.

Probably an interesting example of the concept of the utility of Turing in-completeness in defining "safe, non-abusable" functions.

38.88.188.18 (talk) 18:09, 15 June 2015 (UTC)

A classic example is lambda calculus.

This phrase in the definition is confusing.

What does it mean? A classic example of a Turing complete system is Lamba calculus? — Preceding unsigned comment added by Fredguth (talk • contribs) 14:48, 2 August 2015 (UTC)

Zuse Z3

To clarify a recent edit by User:Dave92F1 that User:TedColes reverted, the first Turing complete computer was Charles Babbage's Analytical Engine, but he never completed it. AFAIK the Z3 was the first operational stored program digital computer. I urge to redo his edit with appropriate references from Z3 (computer) and an exploanation that the Analytical engine was never completed. I also urge TedColes to indicate whether that would satisfy his objections. Shmuel (Seymour J.) Metz Username:Chatul (talk) 17:09, 27 December 2016 (UTC)

statement of incompleteness theorem incorrect

In the "History" section, the brief text pertaining to the completeness and incompleteness theorems reads, "These rules were proved by Kurt Gödel in 1930 to be enough to produce every theorem. However, they will always prove some theorems as both true and false, for an axiomatization not simpler than Peano arithmetic."

I would be in favor of rewriting the whole paragraph more precisely, but, reading the current text as generously as possible, the second sentence gets things importantly backwards. Making the usual assumption of omega-consistency (as in Gödel's original proof) or simple consistency (as in Rosser's improvement), the formal system consisting of the deductive rules (of the first-order calculus) and the axioms (of a modest fragment of arithmetic) will be incomplete, not inconsistent. If, at a first pass, we were to retain the somewhat-loose language of the current description, we'd have to say not that the system "will prove some theorems as both true and false," but something like, "the system will prove some theorems as neither true nor false". But, of course, this is just to say that the system does not prove them: neither P nor ~P are theorems of the system (in the ordinary senses of "theorem" and "prove").

I'm adding this to Talk for the moment rather than correcting it directly on the possibility that I've drastically misunderstood the author's intent...

--Sunyataivarupam (talk) 20:29, 22 March 2017 (UTC)

The entire section seems to desperately need revision, but the sentence you mentioned was particularly bad. I removed it. The rest of the section also needs rewriting. — Carl (CBM · talk) 12:08, 23 March 2017 (UTC)

C isn't Turing-complete

I will argue here that C isn't Turing-complete. Often, a programming language fails to be Turing-complete if it operates on a finite memory, which is necessary for Turing-completeness, since a Turing-machine needs an infinite memory. In the C specification, the sizeof keyword needs an int (or long) result. Since th sizeof() any object in C must be a finite size, C can never be Turing-complete, because it can't address an infinite memory. — Preceding unsigned comment added by 180.174.6.5 (talk) 07:30, 26 July 2018 (UTC)

So which programming languages are Turing-complete in that sense? Guy Harris (talk) 07:33, 26 July 2018 (UTC)

Well, example:the Brainfuck idea(All of the implememtations are not Turing-complete, but the idea is). — Preceding unsigned comment added by 180.174.6.5 (talk • contribs) 11:22, 26 July 2018 (UTC)

BrianFuck is only turing complete if it's pointers are also infinite because it uses indirection. It's generally accepted that computers with finite memory are indeed turing complete - because if you hold with the requirement for infinite memory then nothing can every be turing complete - and the concept loses 100% of it's practical value. So for all practical purposes, C is indeed turing complete. SteveBaker (talk) 19:52, 3 July 2019 (UTC)

No, it's not accepted that computers with finite memory are Turing complete. Also, you cannot just say that a mathematical concept (Turing completeness) can be used for things which do not pass its mathematical definition "for practical reasons". It's like saying that in mathematics there are infinitely many natural numbers, but for every practical reason only finitely many of them are used, so there are finitely many natural numbers. It's simply not true. I explained below how Turing completeness can be claimed for programming languages (as opposed to their implementations).123unoduetre (talk) 16:31, 29 April 2020 (UTC)

I gonna explain why C is not Turing complete (but its subset might be) in a precise way. The operator & can be applied to any variable, so for every variable there exists a possible pointer to it. C contains both the sizeof operator and pointers. The sizeof operator must return an integer. Integers must be finite (as opposed to e.g. floats). The sizeof operator can be applied to a pointer type (not an actual pointer, but the type itself). It means the sizeof operator must return one specific finite number for a specific pointer type. It means there is only a finite amount of memory available for a pointer, so C cannot address infinite memory with its pointers. Nevertheless, if a subset of C is considered (e.g. no sizeof operator which can be applied to types, but only to actual pointers), maybe it is possible for it to be truly Turing complete. So I think we might leave C, but maybe add a small note. Also the statement that "no programming language is Turing complete" is false. It is important to make a distinction between a language (an abstract object) and its implementation. No implementation is truly Turing complete, because no real computer is. But an abstract description of a language can be and many of them indeed are (maybe with some restrictions as discussed above with respect to C). Not all programming languages need that restriction, e.g. if they do not use pointers but references (like e.g. Java or Lisp). There might be other elements which might need to be restricted in some ways of course and it requires careful attention to details of a particular programming language.123unoduetre (talk) 16:06, 29 April 2020 (UTC)

Digital Physics Section

Not only is the Digital Physics section unfounded, it's wrong. Physical behaviors of the universe at the sub-atomic level are not computable, they are only statistically simulatable. The statement "All known laws of physics have consequences that are computable by a series of approximations on a digital computer" is a further bogey. What it means is that at some point you have to stop making the approximation more precise in order to proceed. But if you don't have infinite precision then you have not computed the behavior of the universe properly. Unless you intend to keep recursing until you have infinite precision. Which is either not digital computation or is not going to conclude the calculation of the first millisecond of motion of your first electron before the universe ends. Which means the subject doesn't fit in the context of this page.

192.91.173.36 (talk) 11:02, 25 October 2018 (UTC)

Yes and no. It depends on what you mean by consequence and what Interpretations of quantum mechanics you are using. You can predict the evolution of the state and as long as you don't believe that the wave function is physical; that lets you calculate the consequences. OTOH, if the collapse is physical then the consequences include the collapse, which you can't calculate (although you can calculate a probability distribution.) Shmuel (Seymour J.) Metz Username:Chatul (talk) 16:08, 26 October 2018 (UTC)

Powerpoint

A while back, Tom Wildenhain wrote a paper for SIGBOVIK (a parody conference at which computer scientists get to post academic jokes and be silly) about PowerPoint being Turing-complete. This circulated online and has, more than once, been cited here. I have removed it, and left a commented-out warning because, well, SIGBOVIK. However, it now occurs to me that this deliberately-silly paper may nonetheless be scientifically valid.

I am completely unqualified to judge whether this actually is the case. I recognize many jokes, but other parts could be genuinely serious?

Could anyone who genuinely understands the topic read Wildenhain's article and determine to what extent it can be trusted? Thanks. DS (talk) 18:54, 31 May 2019 (UTC)

While the paper is written in a funny way, it stems directly from the fact that powerpoint is really a Turing-complete machine. The paper in itself doesn't includes a proof, so it might be interesting to link the pptx file, which contains the turing machine, or the video, that explains how the turing machine works. Several of the other software in the list rely on a source that is basically (or redirects directly to) a video showing how the machine works, so having the paper and the video seems acceptable as source for such an anecdotal subject. Alegui (talk) 07:01, 12 November 2019 (UTC)

Weasel word in first paragraph, or not?

The first paragraph says that "Virtually all programming languages today are Turing complete". After consulting WP:WEASEL's page, I believe that it should be replaced with a percentage and a source. The reason that I have not labelled it with a Weasel tag is that it might be exempt from the rule (being in the lead section of the article). --MaxWilderD (talk) 19:18, 27 October 2019 (UTC)

Don't need a conditional (OR a LUT/multiply) to be Turing complete.

About 7 3/4 years ago (see section "Don't need a conditional", above) - I pointed out that you can emulate a Turing-complete language ("SUBLEQ") using a machine that doesn't have a conditional jump instruction - which contradicts what our article says (and the 'common wisdom' about Turing-completeness). I included the complete C source code for a complete emulator as evidence that I'm right - it's only about 20 lines of C code so it's easy to check.

Some people objected (unfairly, IMHO) to the lookup table at the beginning - and I just (very belatedly) realized that you don't need it. Also, you don't need the multiply instruction.

Here is the revised version of my 8-bit SUBLEQ emulator - which must therefore be Turing complete despite having no conditional code whatever:

 // Initialization:
 typedef unsigned char byte ;
 byte mem [...whatever...] = { ...whatever... } ;  // The initial state of memory in the SUBLEQ machine
 int PC = 0 ; // The SUBLEQ machine's program counter.

 // Runtime:
 while ( 1 )
 {
   // Read instruction operands from the program counter location.
   int a = mem[PC++] ;
   int b = mem[PC++] ;
   int c = mem[PC++] ;
   // Perform subtraction:
   mem[b] -= mem[a] ;
   // Extract sign of (mem[b]-1) (presuming 2's complement arithmetic and an 8 bit byte):
   byte x = (mem[b]-1) & 0x80 ;
   // Replicate the sign bit through the entire word:
   x = x | (x>>1) | (x>>2) | (x>>3) | (x>>4) | (x>>5) | (x>>6) | (x>>7) ; // x is either 0xFF or 0x00.
   // c is added to the emulated program counter if (mem[b]<0)
   PC += x & c ;
 }

The problem here is that although I'm CLEARLY correct in proving that you do not need a conditional instruction of any kind to be turing complete - we still can't update the article to say that because nobody can find a reference to back me up - and WP:NOR clearly applies.

This is one of those WikiGodel problems - here is a true statement - which cannot be expressed in Wikipedia!

Does anyone have any ideas about where this could be published without too much hassle so we can use it as a reference? SteveBaker (talk) 19:49, 3 July 2019 (UTC)