![]() | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 |
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)
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 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.
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.
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
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.
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.
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.
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)
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.
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.
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?
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)
(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)
(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)
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)
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)
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
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)
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.
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)
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)
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)
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.
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)
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)
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)
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)
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)
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)
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)
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)
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.
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)
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)
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)
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)
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) {
....
}
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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.
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)
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)
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)
![]() | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 |
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)
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 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.
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.
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
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.
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.
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.
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)
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.
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.
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?
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)
(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)
(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)
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)
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)
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
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)
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.
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)
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)
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)
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.
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)
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)
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)
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)
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)
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)
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)
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)
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.
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)
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)
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)
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)
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) {
....
}
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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.
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)
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)
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)