Talk:Turing completeness/Archive 1

3379:

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.

2584:. 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) 75:

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.

1369:. (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 3400:

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.

3071:

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 "

2554:(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 227:--- 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. 1784:

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

31: 313:) 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. 2860:

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

1900:

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.

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

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.

3542:// Runtime: while ( 1 ) { // Read instruction operands from the program counter location. int a = mem ; int b = mem ; int c = mem ; // Perform subtraction: mem -= mem ; // Extract sign of (mem-1) (presuming 2's complement arithmetic and an 8 bit byte): byte x = (mem-1) & 0x80 ; // Replicate the sign bit through the entire word: x = x | (x: --> 624:). 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. 2899:

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)

2833:

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.

2681:

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

3456:(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 716:

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.

2720:// Initialization: typedef unsigned char byte ; int lut = { 1, 1, 1, 1, 1, 1, 1, .... // 128 ones. 0, 0, 0, 0, 0, 0, 0, .... // 128 zeroes. } ; byte mem = { ...whatever... } ; // The initial state of memory in the SUBLEQ machine int PC = 0 ; // The SUBLEQ machine's program counter. 177:) 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. -- 3485:

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

3203:

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

2730:

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

2615:

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

2553:

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*

1276:

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,

535:

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.

212:

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

104:

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

3427:

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

2479:

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

1930:

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

1879:

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,

1832:

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

981:

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

516:

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

300:

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

74:

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

3272:

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)

1765:

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

1585:

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

1562:

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.

792:

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

404:

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

79:

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

78:

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.

3342:

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

3207:

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

2879:

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

2859:

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

2767:

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

2110:

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

2087:

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

1828:

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

1606:

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

1407:

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

435:

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

414:

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

308:

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

2898:

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

2777:

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

2139:

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

2127:

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

1939:

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

82:

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

3399:

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

3018:

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

2501:

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

1783:

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

1581:

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

994:

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

295:

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

2832:

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

1988:

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.

1899:

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

1809:

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

3378:

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.

3070:

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

1136:

Knowledge 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

492:

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

476:

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

400:

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

3357:

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

1962:

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

1417:

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

447:

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

2680:

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

329:

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

724:

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,

1642:

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

1620:, 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. 1427:

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

3358:

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

2140:

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.

1925:

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

715:

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

83:

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.

3529:

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

2524:"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." 615:

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.

1393:

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

1454:

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

2816:

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

2311:

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

1159:

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. —

2349:

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.

1115:

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

2315:

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

1461:(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); 1364:

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

584:

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

1319:

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.

1989:

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.

1963:

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?

423:

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:

1824:

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

1503:

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

2326:

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?

3486:

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.

86:

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.

746:

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

2410:

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?

1055:

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.

1829:

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.

1349:(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? 291:

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.

309:

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

330:

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.

1766:

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?

2470:

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.

2032:

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.

430:

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.

2091:"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" 2654:

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:

1014:

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.

901:

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

1705:, "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. 2291:

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. --

282:

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.

3510:'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). -- 2620:

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?

1940:

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. --

2502:

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?

2446:

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

1089:, 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 2874:

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

1186:

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

2913:'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. 2639:

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

2224: 2807:

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

3565:

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

2228: 1586:

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

1398:

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.

249:

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?

2727:(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<=0)). 3539:// Initialization: typedef unsigned char byte ; byte mem = { ...whatever... } ; // The initial state of memory in the SUBLEQ machine int PC = 0 ; // The SUBLEQ machine's program counter. 2799:

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

2158:

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.

3533:

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.

325:

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.

2220: 1708:

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.

943: 2216: 2731:

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.

2705:

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

1790:

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.

1761:

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

974: 1693:

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

131:

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,

3249:

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

2953:

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.

2088:

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

768:

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.

3530:

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.

1852:

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:

1672:

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.

1458:(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); 150:

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

1251:

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?

2812:

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

2365:"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." 3216:. 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 2369:

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.

162:

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.

1315:

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,

814:

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?

427:

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

1833:

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!

3208:

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

296:

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.

3585: 3231:

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...

345:

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.

865:

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.--

652:

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.

2711:

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.

1450:

Less than 15 hours after my previous comment, you reverted the article (again), saying "No discussion, so restore". I am unable to guarantee even

2600: 1730:

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

1547:. 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. 1418:

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.

3184:

and an exploanation that the Analytical engine was never completed. I also urge TedColes to indicate whether that would satisfy his objections.

2999:

Please include a definition of "single-taped" as it is difficult to find and this is needed to help make the article understandable. Thanks. -

2855:

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

3536:

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

3273:

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.

193:

I've revised the introductory section in accordance with my (1)-(3) above, and trust that others will make further revisions as appropriate. --

2714:

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.

1217:

It is you yourself who removed a large amount of text without discusssion. Please do not again make such a change without discussion here. —

397:

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

3038: 2215:

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

3424: 2956:

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?

2534: 2111:

Turing machine where the program and input is set beforehand and then the machine runs automatically. I agree that this is just semantics.

1865: 2880:

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

2979:

It is important because it is believed that anything Turing-complete is able to do everything that any classical computer could ever do.

3404: 2920: 2063: 2014: 1990: 1970: 1840: 1715: 2187: 1880:

which by the way shouldn't even be that much of a limitation, as nothing stops you from attaching a harddrive with infinite memory. --

3107: 2561: 2483: 2376: 2040: 697:

is computable on a universal Turing machine, which would imply that no computer more powerful than a UTM can be physically built (see

383: 234: 3332: 3280: 3103:

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

2900: 2328: 2007:

Using the term you are defining in the definition is a horrible idea. "What's catflapping? It's what a catflap does." Meaningless.

478: 90: 3470:

Could anyone who genuinely understands the topic read Wildenhain's article and determine to what extent it can be trusted? Thanks.

2395:

I believe Turing-powerful is a synonym of Turing-complete. There's currently no mention of the phrase Turing-powerful on the wiki.

1814:

If anybody can confirm this, it should be added to the article as it would be a quite an illustrative example (pardon the pun). --

2616:

TC" is tautological/oxymoronic. It doesn't matter whether the language has a native Halt command, it only matters whether it can

1063: 1030: 2821:

conditional-jumps because I have devised a way to make an undeniably turing-complete machine using no-conditional-jump hardware.

1475:. In my opinion, your present version of the article has performed editorial surgery so drastic that it has killed the patient. 3100:

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

1582:

word. In particular, "the most primitive computer" would include my pocket calculator, which is certainly not Turing complete.

2304:

While I think "functional completeness" and "Turing completeness" are very closely related things, the discussion here and at

2116:

Is a person who knows how to simulate a Turing Machine and has a notebook with lots of paper Turing-complete? I guess so...

338:

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

3144: 2128:

clicks. This is not so far away from classical programming and thus does not hinder spreadsheeds from being Turing complete.

2778:

have completely given up on making the article clear, because I don't think there are any sources that describe it. — Carl

3475: 3031: 3556:

7) ; // x is either 0xFF or 0x00. // c is added to the emulated program counter if (mem<0) PC += x & c ; }

913:

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

517:

can prove me wrong and point to some detailed explanation/proof. Until then I think C should be removed (maybe C++ too).

3576:

Does anyone have any ideas about where this could be published without too much hassle so we can use it as a reference?

2708: 2305: 2197:). That's enough to get you Turing completeness, and is, incidentally, precisely "making decisions based on data". -- 2596: 2183:

If it was never built how can we know that it was Turing complete, ie. being able to perform any computational task?

3180:

was the first operational stored program digital computer. I urge to redo his edit with appropriate references from

2761: 1373:

first giving a correct definition of TC. The mathematical nature of the TC concept should be preserved in any case.

2964: 2734:

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

2067: 218: 113: 38: 2824:

I do agree that the concept of "turing complete" is a little fuzzy around the edges - but we do go on to deny the

135:, a universal Turing machine. (All known Turing-complete systems are Turing-equivalent, which adds support to the 3506:

The first paragraph says that "Virtually all programming languages today are Turing complete". After consulting

3239: 866: 3463:

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

2829: 841: 3471: 1861: 1853: 1048: 621: 408:

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

47: 17: 2538: 3573:

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

3288: 2924: 2707:" - and also that a machine is turing complete if it can simulate a turing complete machine. Note also that 2180:

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

2018: 1719: 3408: 3228:

prove them: neither P nor ~P are theorems of the system (in the ordinary senses of "theorem" and "prove").

3111: 2565: 2487: 2380: 2279: 2246: 2209: 2163: 2044: 1994: 1974: 1844: 920: 379: 238: 3328: 3284: 558:

Yes, that was my point. But I don't know if these languages have other means of simulating unbounded tape.

482: 222: 94: 3384: 3363: 3343:

concept loses 100% of it's practical value. So for all practical purposes, C is indeed turing complete.

2592: 2232: 2145: 1067: 1026: 815: 3140: 3086: 3081:

Since the paragraph in question is otherwise unsupported, I proposed to remove it for discussion here.

3056: 2960: 2904: 2332: 1911: 1047:

is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a

250: 3380: 3359: 2141: 2129: 2101: 733:, or something computationally equivalent. It doesn't matter how it does it, only that it does it. -- 375: 3324: 951: 468:

is ambiguous as to whether Perl an example of a Turing-complete or of a non Turing-complete language.

3581: 3515: 3348: 3320: 3304: 3276: 3235: 3132: 3076: 2984: 2916: 2889: 2865: 2838: 2757: 2686: 2626: 2588: 2557: 2530: 2507: 2372: 2036: 2010: 1966: 1836: 1711: 1366: 1277:

and hiding their meaning by exclusively using the jargon of Turing machines is a little old fasioned.

1059: 1022: 1018: 906:, which is explained concisely, and gives the starting point for what an 'algorithm' is. From there, 773: 676: 617: 590: 541: 371: 230: 136: 2062:

I think that separating between OO and procedural is over simplistic as most languages nowadays are

996: 449: 3136: 2467: 2271: 2242: 1857: 1044: 1000: 625: 559: 518: 453: 1881: 1791: 314: 3487: 3449: 2437: 2400: 2198: 2159: 1815: 1533: 991: 794: 734: 629: 563: 522: 2193:

We can look at Babbage's design and note that it supported loops and conditional branches (see

3173: 3035: 3025: 2320: 2194: 1885: 1795: 1677: 1625: 1552: 1509: 1433: 1354: 1282: 1192: 1142: 3507: 3491: 3433: 3189: 3082: 3052: 3044: 3021: 3004: 2452: 2416: 1773: 1563:

Surely what is meant above is that the set of squares that are not blank is bounded. — Carl

1482: 1380: 1327: 1222: 1165: 1123: 1100: 903: 198: 182: 3519: 3495: 3479: 3437: 3412: 3388: 3367: 3352: 3336: 3308: 3261: 3243: 3193: 3148: 3115: 3090: 3060: 3008: 2988: 2968: 2928: 2908: 2893: 2869: 2842: 2790: 2690: 2630: 2604: 2569: 2542: 2511: 2491: 2456: 2441: 2420: 2404: 2384: 2354: 2336: 2296: 2286: 2264: 2253: 2235: 2201: 2167: 2149: 2132: 2120: 2104: 2077: 2048: 2022: 1998: 1978: 1944: 1914: 1904: 1889: 1869: 1818: 1799: 1777: 1723: 1681: 1655: 1629: 1598: 1575: 1556: 1513: 1486: 1437: 1384: 1358: 1331: 1286: 1226: 1196: 1169: 1146: 1127: 1104: 1071: 1034: 1004: 886: 869: 848: 818: 797: 777: 755: 737: 633: 594: 567: 545: 526: 509: 486: 457: 440: 387: 317: 275: 253: 242: 202: 186: 98: 3577: 3511: 3344: 3300: 3169: 3047: 2980: 2885: 2861: 2834: 2753: 2682: 2622: 2503: 1738:

if it sells every Walmart-obtainable item; likewise, we could say that any other store is

769: 706: 680: 586: 537: 466:"Another famous example is regular expressions, as contained in languages such as Perl." 2825: 2768:

language will be able to simulate SUBLEQ, and so the language will at least be able to

2738: 2261: 1537: 1468: 752: 730: 3128:

What does it mean? A classic example of a Turing complete system is Lamba calculus?

310: 112:— A computational system that can compute every Turing-computable function (i.e., the 3567: 3256: 3181: 3177: 3165: 3161: 2785: 2742: 2433: 2396: 2351: 2249:

deals with sets of functions. Could you explain why they are the 'exact same thing'?

2074: 1650: 1593: 1570: 907: 702: 504: 2881: 2749: 2184: 1734:

if it can be obtained at a Walmart store, and we could say that any other store is

1697:

a term is to not use the term in the definition. That isn't a definition that's an

1673: 1621: 1548: 1505: 1429: 1350: 1278: 1188: 1138: 987: 983: 120:. Alternatively, such a system is one that can simulate a universal Turing machine. 2745:(both of which could loop - but not conditionally) were in fact Turing complete. 3429: 3185: 3000: 2581: 2448: 2412: 2283: 2117: 1901: 1769: 1698: 1478: 1376: 1323: 1218: 1161: 1137:

program acting on integers. A clear definition just de-jargonizes what you said.

1119: 1096: 284: 194: 178: 46:

If you wish to start a new discussion or revive an old one, please do so on the

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

conditionals, and arbitrary while-style loops. Is that too much or too little?

2293: 2250: 1941: 1694: 1536:) whose universality is achieved only by modifying the standard definition of 883: 845: 690: 664: 437: 3524: 3220:

true and false," but something like, "the system will prove some theorems as

2717:

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

3314: 2426: 1702: 272: 3317:

idea(All of the implememtations are not Turing-complete, but the idea is).

3224:

true nor false". But, of course, this is just to say that the system does

2828:

the title of "First computer" because of that lack. The deal is that the

1756:

Turing-complete computational system Walmart-equivalent store <---: -->

1616:

But more substantively--- the input to a Turing machine is required to be

3252: 2781: 2095: 1646: 1589: 1566: 694: 668: 500: 2580:

I originally read this article since it was mentioned as a reference in

1910:

I cannot agree more with you! This 'experiment' is not worth mentioning

1875:

Another example of a non-turning complete language in wide use would be

223:

http://projekte.fast.de/Projekte/forsoft/ocl/4_3Turing_Completeness.html

1471:

article — although it's not perfect, it is informal where appropriate,

647: 2466:

XPath is a is not Turing-complete language but XQuery is according to

1876: 260: 2070:

is any bit as OO as C++ is (with both really being Multi-paradigm).

1543:

Turing machines have "unbounded input". What you meant, I think, is

3525:

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

910:

is your next port of call. My take for a definition is as follows:

2430: 648:

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

1754:

other computational systems Walmart-obtainable <---: -->

1408:

there is no reason not to do so. There is no chance of confusion

448:

communities, rather than in a talk page on a Knowledge article.

259:

I removed the comment from the page. it read: Under traditional

497:

C is a Turing complete language, rather than remove it. — Carl

2058:

Procedural programming languages vs. Object-oriented languages

25: 2974:

Turing complete just means able to simulate a Turing machine.

840:

The Church-Turing thesis cannot be proved, as explained in

882:

Indeed, it's about computability, not about tractability.

2260:

I agree with Mack, they really are the exact same thing.

2175: 1041:

Which part of the following quotation is unclear to you?

472:

Criterion for Turing-complete languages and infinite tape

1752:

compute a function Walmart store <---: -->

217:

A famous example of non-Turing complete language is OCL

3453: 1755:

Turing-computable Walmart-complete store <---: -->

361:

needs proof of equvilance mabey for lambda calculus ?

2319:

Is this relationship something that needs to be more

2308:

has convinced me they are not the "exact same thing".

1473:

without sacrificing the formal definitions altogether

954: 923: 729:

All it needs to be able to do is emulate a universal

1753:

Turing machine other stores <---: -->

165:(1)-(3) is a summary of how I've found these terms ( 2176:

Babbage's analytical engine really Turing complete?

311:

http://www.qubit.org/oldsite/resource/deutsch85.pdf

2521:This statement appears too vague and non-notable: 1532:is sometimes used to distinguish a system (e.g. a 1085:. This definition does not involve the concept of 968: 937: 3168:reverted, the first Turing complete computer was 405:Life, or, well, lots of Turing-complete systems. 2748:Sadly, although this is obviously true - it is 1081:is defined to be a function computable by some 1043:"A computational system that can compute every 353:" 1751:function obtain an item <---: --> 3199:statement of incompleteness theorem incorrect 2582:http://www.php-security.org/downloads/bco.pdf 1805:good non-turing complete language: 3D shaders 158:of system. Some authors also distinguish as 8: 3125:This phrase in the definition is confusing. 3096:Turing Incomplete Languages to prevent abuse 2517:Removing mention to "David Turner" languages 3419:Yes and no. It depends on what you mean by 2884:and disallowed - which is really annoying. 3318: 3274: 3073:Nobody has ever built a universal computer 2914: 1464:(3) maybe include an informal subsection. 962: 961: 953: 931: 930: 922: 3430:Shmuel (Seymour J.) Metz Username:Chatul 3186:Shmuel (Seymour J.) Metz Username:Chatul 3027:The Ultimate Challenge: the 3x+1 problem 986:) and the beginnings of set theory with 394:Explanation of some cleanups of 6/1/04. 3502:Weasel word in first paragraph, or not? 3176:, but he never completed it. AFAIK the 1757:Turing-equivalent computational system 1701:and becomes dangerously close to being 938:{\displaystyle S\subseteq \mathbb {N} } 419:Criterion for Turing-complete languages 3559:The problem here is that although I'm 3066:Turing completeness of extant machines 2698: 2066:and also bluntly wrong as for example 350:Moved the following from the article: 44:Do not edit the contents of this page. 3460:nonetheless be scientifically valid. 3121:A classic example is lambda calculus. 1750:item <---: --> 127:— A Turing-complete system is called 7: 3425:Interpretations of quantum mechanics 2475:SQL is no longer non-Turing Complete 2468:How XQuery extends XPath IBM article 2429:and found one mention in this paper 2083:Turing Completeness vs. Spreadsheets 2064:Multi-paradigm programming languages 1810:constructs if I remember correctly. 3448:A while back, Tom Wildenhain wrote 2549:The need for an explicit HALT state 1746:collection of items as do Walmarts: 1467:For comparison, take a look at the 656:Turing-completeness of the universe 401:better. "Unlimited" would be okay. 267:should be hyphenated, but the noun 1540:so as to include unbounded input. 493:article, we would need to explain 24: 2737:Worse still, that means that the 2480:is no basis for this urban myth. 2270:Merging would be a big mistake — 969:{\displaystyle x\in \mathbb {N} } 1950:The same computational power as 29: 3299:Turing-complete in that sense? 3295:So which programming languages 3267: 990:. Then Russell came along with 213:completely useless on its own. 2870:22:49, 30 September 2011 (UTC) 2843:20:43, 30 September 2011 (UTC) 2791:20:10, 30 September 2011 (UTC) 2762:16:55, 30 September 2011 (UTC) 2724:0. PC += lut+128] * c ; } 1895:thoughtless thought experiment 1: 3496:07:01, 12 November 2019 (UTC) 3428:a probability distribution.) 3194:17:09, 27 December 2016 (UTC) 3032:American Mathematical Society 2909:22:49, 27 February 2013 (UTC) 2752:, so I can't write about it. 2665:} catch(VMHaltException e) { 1945:01:05, 20 February 2007 (UTC) 1890:07:31, 9 September 2010 (UTC) 1682:18:55, 22 February 2010 (UTC) 1656:15:33, 22 February 2010 (UTC) 1630:15:29, 22 February 2010 (UTC) 1599:15:17, 22 February 2010 (UTC) 1576:15:17, 22 February 2010 (UTC) 1557:14:58, 22 February 2010 (UTC) 1514:14:51, 22 February 2010 (UTC) 1487:14:48, 22 February 2010 (UTC) 1438:17:07, 20 February 2010 (UTC) 1385:14:48, 20 February 2010 (UTC) 1359:22:40, 19 February 2010 (UTC) 1332:14:48, 20 February 2010 (UTC) 1287:22:38, 19 February 2010 (UTC) 1227:18:55, 19 February 2010 (UTC) 1197:18:51, 19 February 2010 (UTC) 1170:18:45, 19 February 2010 (UTC) 1147:17:42, 19 February 2010 (UTC) 1105:17:02, 19 February 2010 (UTC) 1072:20:50, 17 February 2010 (UTC) 849:21:51, 19 February 2007 (UTC) 798:00:42, 13 December 2005 (UTC) 756:18:13, 12 December 2005 (UTC) 441:22:13, 19 February 2007 (UTC) 254:11:02, 19 November 2005 (UTC) 203:16:24, 28 November 2007 (UTC) 187:15:55, 28 November 2007 (UTC) 99:06:15, 28 November 2007 (UTC) 3520:19:18, 27 October 2019 (UTC) 3438:16:08, 26 October 2018 (UTC) 3413:11:02, 25 October 2018 (UTC) 3160:To clarify a recent edit by 2894:14:02, 9 December 2011 (UTC) 2803:conditional jumps whatever, 2709:One instruction set computer 2699:Don't need conditional jump. 2691:14:08, 9 December 2011 (UTC) 2457:01:02, 7 December 2007 (UTC) 2442:00:21, 7 December 2007 (UTC) 2421:00:03, 7 December 2007 (UTC) 2405:15:09, 6 December 2007 (UTC) 2385:15:13, 20 October 2007 (UTC) 2306:Talk:Functional completeness 2297:17:15, 2 December 2007 (UTC) 2287:05:32, 2 December 2007 (UTC) 2265:05:16, 2 December 2007 (UTC) 1999:09:05, 10 October 2012 (UTC) 1979:19:52, 17 October 2007 (UTC) 1819:23:42, 23 January 2006 (UTC) 1778:15:09, 21 October 2010 (UTC) 1005:22:17, 16 January 2017 (UTC) 738:03:51, 7 November 2005 (UTC) 720:What is Turing-completeness? 510:11:05, 20 October 2010 (UTC) 487:07:16, 20 October 2010 (UTC) 458:22:26, 16 January 2017 (UTC) 388:16:23, 8 December 2011 (UTC) 144:(Computational) universality 2576:Relivence of HALT'les langs 2512:03:56, 7 January 2011 (UTC) 2492:15:51, 14 August 2010 (UTC) 2254:14:39, 28 August 2007 (UTC) 1954:Turing machine? Which one? 887:14:26, 28 August 2007 (UTC) 263:conventions, the adjective 114:partial recursive functions 3601: 3389:16:06, 29 April 2020 (UTC) 3368:16:31, 29 April 2020 (UTC) 3262:12:08, 23 March 2017 (UTC) 3244:20:29, 22 March 2017 (UTC) 3149:14:48, 2 August 2015 (UTC) 3019:periodic: see for example 2355:07:30, 15 April 2009 (UTC) 2337:01:08, 15 April 2009 (UTC) 2208:We should merge this with 2202:06:27, 30 April 2007 (UTC) 2188:05:32, 30 April 2007 (UTC) 2168:23:42, 17 April 2013 (UTC) 2150:05:05, 20 April 2011 (UTC) 2133:11:09, 13 April 2007 (UTC) 2105:11:00, 31 March 2007 (UTC) 2023:09:37, 3 August 2010 (UTC) 1915:21:16, 20 April 2006 (UTC) 1905:05:11, 28 March 2006 (UTC) 1724:09:32, 3 August 2010 (UTC) 1607:nobody would get confused. 1079:Turing-computable function 1045:Turing-computable function 699:philosophical implications 673:philosophical implications 634:21:02, 27 April 2014 (UTC) 595:07:13, 10 April 2014 (UTC) 219:Object_Constraint_Language 3337:11:22, 26 July 2018 (UTC) 3309:07:33, 26 July 2018 (UTC) 3289:07:30, 26 July 2018 (UTC) 3116:18:09, 15 June 2015 (UTC) 3091:15:46, 28 June 2014 (UTC) 3061:06:55, 28 June 2014 (UTC) 2989:07:20, 29 July 2012 (UTC) 2969:03:38, 29 July 2012 (UTC) 2543:15:14, 4 March 2011 (UTC) 2527:Hence, I'm removing it. 2121:07:03, 1 April 2007 (UTC) 2078:07:56, 9 March 2007 (UTC) 2049:06:57, 4 April 2014 (UTC) 1128:03:15, 30 July 2008 (UTC) 1035:03:00, 30 July 2008 (UTC) 870:06:41, 26 June 2007 (UTC) 778:12:01, 11 July 2009 (UTC) 568:21:48, 9 April 2014 (UTC) 546:17:11, 9 April 2014 (UTC) 527:11:45, 9 April 2014 (UTC) 287:20:13, 28 Oct 2004 (UTC) 276:22:27, 9 March 2006 (UTC) 243:03:13, 9 March 2010 (UTC) 3586:19:49, 3 July 2019 (UTC) 3480:18:54, 31 May 2019 (UTC) 3353:19:52, 3 July 2019 (UTC) 3009:18:55, 7 July 2013 (UTC) 2631:06:15, 19 May 2011 (UTC) 2605:01:46, 19 May 2011 (UTC) 2570:23:07, 18 May 2011 (UTC) 2236:01:24, 3 June 2007 (UTC) 2223:but with google scholar 1870:16:37, 30 May 2009 (UTC) 1800:17:10, 29 May 2014 (UTC) 1049:universal Turing machine 671:is Turing-complete (see 622:Linear_bounded_automaton 318:20:47, 5 July 2006 (UTC) 18:Talk:Turing completeness 3395:Digital Physics Section 3268:C isn't Turing-complete 2929:15:08, 4 May 2015 (UTC) 2280:functional completeness 2247:functional completeness 2225:Functional completeness 2221:Functional completeness 2210:Functional completeness 1921:Unacceptable Definition 819:16:54, 1 May 2006 (UTC) 464:I think the context of 3467:be genuinely serious? 970: 939: 867:ANONYMOUS COWARD0xC0DE 221:Here is a good proof. 2245:deals with automata, 971: 940: 156:Turing-complete class 146:— A system is called 42:of past discussions. 3204:Peano arithmetic." 3022:Lagarias, Jeffrey C. 2830:Church–Turing thesis 1958:Turing machine? But 1367:Church-Turing thesis 952: 921: 842:Church–Turing thesis 677:Church-Turing thesis 618:Finite-state_machine 137:Church-Turing thesis 2772:a conditional jump. 2272:Turing-completeness 2243:turing completeness 2229:Turing completeness 2217:Turing completeness 2094:See the article on 1087:Turing completeness 415:far as I can tell. 269:Turing completeness 133:and be simulated by 110:Turing-completeness 3313:Well, example:the 2703:The article says " 2098:for more on this. 1740:Walmart-equivalent 1732:Walmart-obtainable 1534:cellular automaton 995:modern computing. 966: 935: 334:jef@jefraskin.com 154:with respect to a 125:Turing-equivalence 3570:clearly applies. 3339: 3323:comment added by 3291: 3279:comment added by 3260: 3174:Analytical Engine 3152: 3135:comment added by 3040:978-0-8218-4940-8 2931: 2919:comment added by 2789: 2608: 2593:Aryeh M. Friedman 2591:comment added by 2560:comment added by 2533:comment added by 2387: 2375:comment added by 2323:in both articles? 2241:I object though, 2195:Analytical engine 2039:comment added by 2013:comment added by 1981: 1969:comment added by 1839:comment added by 1714:comment added by 1654: 1597: 1574: 1062:comment added by 1037: 1021:comment added by 992:Russell's_paradox 982:and friends, see 917:recursive subset 693:by some that the 667:by some that the 508: 391: 374:comment added by 233:comment added by 171:Turing equivalent 129:Turing equivalent 67: 66: 54: 53: 48:current talk page 3592: 3250: 3151: 3129: 3051: 2961:Billyshiverstick 2779: 2607: 2585: 2572: 2545: 2425:I just searched 2370: 2051: 2025: 1964: 1848: 1744:exactly the same 1736:Walmart-complete 1726: 1644: 1587: 1564: 1530:weakly universal 1074: 1016: 975: 973: 972: 967: 965: 944: 942: 941: 936: 934: 904:Effective_method 793:the article. -- 498: 411:-D. Cristofani. 390: 368: 245: 160:weakly universal 63: 56: 55: 33: 32: 26: 3600: 3599: 3595: 3594: 3593: 3591: 3590: 3589: 3557: 3540: 3527: 3504: 3446: 3397: 3270: 3236:Sunyataivarupam 3201: 3170:Charles Babbage 3158: 3130: 3123: 3098: 3068: 3041: 3020: 3016: 3014:Weakly complete 2997: 2951: 2725: 2721: 2701: 2669: 2663: 2651: 2586: 2555: 2551: 2528: 2519: 2499: 2477: 2393: 2391:Turing-powerful 2367: 2233:Mack the Turtle 2213: 2178: 2085: 2060: 2034: 2008: 1937: 1923: 1897: 1834: 1807: 1758: 1709: 1091:Turing-complete 1057: 950: 949: 919: 918: 722: 712:Justification: 707:digital physics 681:digital physics 658: 650: 474: 421: 369: 265:Turing-complete 228: 167:Turing complete 118:Turing-complete 105:machine, etc.): 72: 59: 30: 22: 21: 20: 12: 11: 5: 3598: 3596: 3541: 3538: 3526: 3523: 3503: 3500: 3499: 3498: 3445: 3442: 3441: 3440: 3416: 3415: 3396: 3393: 3392: 3391: 3375: 3374: 3373: 3372: 3371: 3370: 3311: 3269: 3266: 3265: 3264: 3200: 3197: 3157: 3154: 3122: 3119: 3106: 3097: 3094: 3067: 3064: 3039: 3024:, ed. (2010). 3015: 3012: 2996: 2993: 2992: 2991: 2976: 2975: 2950: 2944: 2943: 2942: 2941: 2940: 2939: 2938: 2937: 2936: 2935: 2934: 2933: 2932: 2848: 2847: 2846: 2845: 2826:Harvard Mark I 2822: 2794: 2793: 2774: 2773: 2739:Harvard Mark I 2722: 2719: 2700: 2697: 2696: 2695: 2694: 2693: 2674: 2667: 2661: 2658: 2653: 2649: 2646: 2644: 2643: 2642: 2641: 2634: 2633: 2611: 2550: 2547: 2535:131.114.88.220 2518: 2515: 2498: 2495: 2476: 2473: 2464: 2463: 2462: 2461: 2460: 2459: 2392: 2389: 2366: 2363: 2362: 2361: 2360: 2359: 2358: 2357: 2342: 2341: 2340: 2339: 2324: 2317: 2313: 2309: 2274:is definitely 2268: 2267: 2257: 2256: 2212: 2206: 2205: 2204: 2177: 2174: 2173: 2172: 2171: 2170: 2153: 2152: 2136: 2135: 2124: 2123: 2113: 2112: 2084: 2081: 2059: 2056: 2055: 2054: 2053: 2052: 2027: 2026: 2004: 2003: 2002: 2001: 1983: 1982: 1936: 1933: 1922: 1919: 1918: 1917: 1896: 1893: 1873: 1872: 1858:Damian Yerrick 1822: 1821: 1806: 1803: 1781: 1780: 1767: 1749: 1748: 1747: 1691: 1690: 1689: 1688: 1687: 1686: 1685: 1684: 1663: 1662: 1661: 1660: 1659: 1658: 1635: 1634: 1633: 1632: 1611: 1610: 1609: 1608: 1579: 1578: 1545:infinite input 1538:Turing machine 1523: 1522: 1521: 1520: 1519: 1518: 1517: 1516: 1494: 1493: 1492: 1491: 1490: 1489: 1476: 1469:Turing machine 1465: 1462: 1459: 1456: 1443: 1442: 1441: 1440: 1422: 1421: 1420: 1419: 1412: 1411: 1410: 1409: 1402: 1401: 1400: 1399: 1388: 1387: 1374: 1347: 1346: 1345: 1344: 1343: 1342: 1341: 1340: 1339: 1338: 1337: 1336: 1335: 1334: 1321: 1300: 1299: 1298: 1297: 1296: 1295: 1294: 1293: 1292: 1291: 1290: 1289: 1263: 1262: 1261: 1260: 1259: 1258: 1257: 1256: 1255: 1254: 1253: 1252: 1238: 1237: 1236: 1235: 1234: 1233: 1232: 1231: 1230: 1229: 1206: 1205: 1204: 1203: 1202: 1201: 1200: 1199: 1177: 1176: 1175: 1174: 1173: 1172: 1152: 1151: 1150: 1149: 1131: 1130: 1117: 1112: 1111: 1110: 1109: 1108: 1107: 1094: 1083:Turing machine 1012: 1011: 1010: 1009: 1008: 1007: 979: 978: 977: 964: 960: 957: 933: 929: 926: 894: 893: 892: 891: 890: 889: 875: 874: 873: 872: 860: 859: 858: 857: 856: 855: 854: 853: 852: 851: 829: 828: 827: 826: 825: 824: 823: 822: 816:134.117.196.45 805: 804: 803: 802: 801: 800: 785: 784: 783: 782: 781: 780: 761: 760: 759: 758: 741: 740: 731:Turing machine 721: 718: 660:Changed this: 657: 654: 649: 646: 645: 644: 643: 642: 641: 640: 639: 638: 637: 636: 604: 603: 602: 601: 600: 599: 598: 597: 575: 574: 573: 572: 571: 570: 551: 550: 549: 548: 530: 529: 513: 512: 473: 470: 462: 461: 460: 444: 443: 420: 417: 366: 364: 359: 357: 348: 347: 346: 337: 332: 331: 323: 322: 321: 320: 303: 302: 289: 280: 279: 278: 247: 215: 210: 208: 206: 205: 190: 189: 163: 140: 121: 106: 71: 68: 65: 64: 52: 51: 34: 23: 15: 14: 13: 10: 9: 6: 4: 3: 2: 3597: 3588: 3587: 3583: 3579: 3574: 3571: 3569: 3564: 3563: 3537: 3534: 3531: 3522: 3521: 3517: 3513: 3509: 3501: 3497: 3493: 3489: 3484: 3483: 3482: 3481: 3477: 3473: 3468: 3466: 3461: 3459: 3455: 3451: 3443: 3439: 3435: 3431: 3426: 3422: 3418: 3417: 3414: 3410: 3406: 3405:192.91.173.36 3403: 3402: 3401: 3394: 3390: 3386: 3382: 3377: 3376: 3369: 3365: 3361: 3356: 3355: 3354: 3350: 3346: 3341: 3340: 3338: 3334: 3330: 3326: 3322: 3316: 3312: 3310: 3306: 3302: 3298: 3294: 3293: 3292: 3290: 3286: 3282: 3278: 3263: 3258: 3254: 3248: 3247: 3246: 3245: 3241: 3237: 3232: 3229: 3227: 3223: 3219: 3215: 3211: 3205: 3198: 3196: 3195: 3191: 3187: 3183: 3182:Z3 (computer) 3179: 3175: 3171: 3167: 3166:User:TedColes 3163: 3162:User:Dave92F1 3155: 3153: 3150: 3146: 3142: 3138: 3134: 3126: 3120: 3118: 3117: 3113: 3109: 3104: 3101: 3095: 3093: 3092: 3088: 3084: 3079: 3077: 3074: 3065: 3063: 3062: 3058: 3054: 3049: 3046: 3042: 3037: 3033: 3029: 3028: 3023: 3013: 3011: 3010: 3006: 3002: 2994: 2990: 2986: 2982: 2978: 2977: 2973: 2972: 2971: 2970: 2966: 2962: 2957: 2954: 2948: 2945: 2930: 2926: 2922: 2921:183.78.207.48 2918: 2912: 2911: 2910: 2906: 2902: 2897: 2896: 2895: 2891: 2887: 2883: 2878: 2877:unconditional 2873: 2872: 2871: 2867: 2863: 2858: 2854: 2853: 2852: 2851: 2850: 2849: 2844: 2840: 2836: 2831: 2827: 2823: 2820: 2815: 2811: 2806: 2802: 2798: 2797: 2796: 2795: 2792: 2787: 2783: 2776: 2775: 2771: 2766: 2765: 2764: 2763: 2759: 2755: 2751: 2746: 2744: 2743:Z3 (computer) 2740: 2735: 2732: 2728: 2718: 2715: 2712: 2710: 2706: 2692: 2688: 2684: 2679: 2678: 2677: 2676: 2675: 2672: 2666: 2660: 2656: 2648: 2638: 2637: 2636: 2635: 2632: 2628: 2624: 2619: 2614: 2613: 2612: 2609: 2606: 2602: 2598: 2594: 2590: 2583: 2578: 2577: 2573: 2571: 2567: 2563: 2559: 2548: 2546: 2544: 2540: 2536: 2532: 2525: 2522: 2516: 2514: 2513: 2509: 2505: 2496: 2494: 2493: 2489: 2485: 2481: 2474: 2472: 2469: 2458: 2454: 2450: 2445: 2444: 2443: 2439: 2435: 2431: 2428: 2424: 2423: 2422: 2418: 2414: 2409: 2408: 2407: 2406: 2402: 2398: 2390: 2388: 2386: 2382: 2378: 2374: 2364: 2356: 2353: 2348: 2347: 2346: 2345: 2344: 2343: 2338: 2334: 2330: 2325: 2322: 2318: 2314: 2310: 2307: 2303: 2302: 2301: 2300: 2299: 2298: 2295: 2289: 2288: 2285: 2281: 2278:the same as " 2277: 2273: 2266: 2263: 2259: 2258: 2255: 2252: 2248: 2244: 2240: 2239: 2238: 2237: 2234: 2230: 2226: 2222: 2218: 2211: 2207: 2203: 2200: 2199:Robert Merkel 2196: 2192: 2191: 2190: 2189: 2186: 2181: 2169: 2165: 2161: 2160:Ben Standeven 2157: 2156: 2155: 2154: 2151: 2147: 2143: 2138: 2137: 2134: 2131: 2126: 2125: 2122: 2119: 2115: 2114: 2109: 2108: 2107: 2106: 2103: 2099: 2097: 2092: 2089: 2082: 2080: 2079: 2076: 2071: 2069: 2065: 2057: 2050: 2046: 2042: 2038: 2031: 2030: 2029: 2028: 2024: 2020: 2016: 2015:184.91.37.207 2012: 2006: 2005: 2000: 1996: 1992: 1991:92.60.245.178 1987: 1986: 1985: 1984: 1980: 1976: 1972: 1971:60.234.168.92 1968: 1961: 1957: 1953: 1949: 1948: 1947: 1946: 1943: 1934: 1932: 1929: 1920: 1916: 1913: 1912:82.229.209.33 1909: 1908: 1907: 1906: 1903: 1894: 1892: 1891: 1887: 1883: 1878: 1871: 1867: 1863: 1859: 1856:-complete. -- 1855: 1851: 1850: 1849: 1846: 1842: 1841:131.107.0.106 1838: 1830: 1826: 1820: 1817: 1816:Robert Merkel 1813: 1812: 1811: 1804: 1802: 1801: 1797: 1793: 1789: 1788: 1779: 1775: 1771: 1764: 1760: 1759: 1745: 1741: 1737: 1733: 1729: 1728: 1727: 1725: 1721: 1717: 1716:184.91.37.207 1713: 1706: 1704: 1700: 1696: 1683: 1679: 1675: 1671: 1670: 1669: 1668: 1667: 1666: 1665: 1664: 1657: 1652: 1648: 1641: 1640: 1639: 1638: 1637: 1636: 1631: 1627: 1623: 1619: 1615: 1614: 1613: 1612: 1605: 1604: 1603: 1602: 1601: 1600: 1595: 1591: 1583: 1577: 1572: 1568: 1561: 1560: 1559: 1558: 1554: 1550: 1546: 1541: 1539: 1535: 1531: 1526: 1515: 1511: 1507: 1502: 1501: 1500: 1499: 1498: 1497: 1496: 1495: 1488: 1484: 1480: 1474: 1470: 1466: 1463: 1460: 1457: 1455:alternatives: 1453: 1449: 1448: 1447: 1446: 1445: 1444: 1439: 1435: 1431: 1426: 1425: 1424: 1423: 1416: 1415: 1414: 1413: 1406: 1405: 1404: 1403: 1397: 1392: 1391: 1390: 1389: 1386: 1382: 1378: 1372: 1368: 1363: 1362: 1361: 1360: 1356: 1352: 1333: 1329: 1325: 1318: 1314: 1313: 1312: 1311: 1310: 1309: 1308: 1307: 1306: 1305: 1304: 1303: 1302: 1301: 1288: 1284: 1280: 1275: 1274: 1273: 1272: 1271: 1270: 1269: 1268: 1267: 1266: 1265: 1264: 1250: 1249: 1248: 1247: 1246: 1245: 1244: 1243: 1242: 1241: 1240: 1239: 1228: 1224: 1220: 1216: 1215: 1214: 1213: 1212: 1211: 1210: 1209: 1208: 1207: 1198: 1194: 1190: 1185: 1184: 1183: 1182: 1181: 1180: 1179: 1178: 1171: 1167: 1163: 1158: 1157: 1156: 1155: 1154: 1153: 1148: 1144: 1140: 1135: 1134: 1133: 1132: 1129: 1125: 1121: 1114: 1113: 1106: 1102: 1098: 1092: 1088: 1084: 1080: 1076: 1075: 1073: 1069: 1065: 1061: 1054: 1053: 1052: 1050: 1046: 1040: 1039: 1038: 1036: 1032: 1028: 1024: 1020: 1006: 1002: 998: 993: 989: 985: 980: 958: 955: 948: 927: 924: 916: 912: 911: 909: 908:Recursive_set 905: 900: 899: 898: 897: 896: 895: 888: 885: 881: 880: 879: 878: 877: 876: 871: 868: 864: 863: 862: 861: 850: 847: 843: 839: 838: 837: 836: 835: 834: 833: 832: 831: 830: 820: 817: 813: 812: 811: 810: 809: 808: 807: 806: 799: 796: 795:Robert Merkel 791: 790: 789: 788: 787: 786: 779: 775: 771: 767: 766: 765: 764: 763: 762: 757: 754: 750: 745: 744: 743: 742: 739: 736: 735:Robert Merkel 732: 728: 727: 726: 719: 717: 713: 710: 708: 704: 703:Church-Turing 700: 696: 692: 687: 684: 682: 678: 674: 670: 666: 661: 655: 653: 635: 631: 627: 623: 619: 614: 613: 612: 611: 610: 609: 608: 607: 606: 605: 596: 592: 588: 583: 582: 581: 580: 579: 578: 577: 576: 569: 565: 561: 557: 556: 555: 554: 553: 552: 547: 543: 539: 534: 533: 532: 531: 528: 524: 520: 515: 514: 511: 506: 502: 496: 491: 490: 489: 488: 484: 480: 471: 469: 467: 459: 455: 451: 446: 445: 442: 439: 436:languages. -- 434: 433: 432: 428: 425: 418: 416: 412: 409: 406: 402: 398: 395: 392: 389: 385: 381: 377: 373: 365: 362: 358: 355: 351: 344: 343: 342: 339: 335: 328: 327: 326: 319: 316: 312: 307: 306: 305: 304: 299: 298: 297: 293: 288: 286: 277: 274: 271:need not be. 270: 266: 262: 258: 257: 256: 255: 252: 251:70.194.26.134 246: 244: 240: 236: 232: 225: 224: 220: 214: 209: 204: 200: 196: 192: 191: 188: 184: 180: 176: 172: 168: 164: 161: 157: 153: 149: 145: 141: 138: 134: 130: 126: 122: 119: 115: 111: 107: 103: 102: 101: 100: 96: 92: 88: 84: 80: 76: 69: 62: 58: 57: 49: 45: 41: 40: 35: 28: 27: 19: 3575: 3572: 3561: 3560: 3558: 3554:6) | (x: --> 3552:5) | (x: --> 3550:4) | (x: --> 3548:3) | (x: --> 3546:2) | (x: --> 3544:1) | (x: --> 3535: 3532: 3528: 3505: 3469: 3464: 3462: 3457: 3447: 3420: 3398: 3381:123unoduetre 3360:123unoduetre 3319:— Preceding 3296: 3275:— Preceding 3271: 3233: 3230: 3225: 3221: 3217: 3214:inconsistent 3213: 3209: 3206: 3202: 3159: 3131:— Preceding 3127: 3124: 3108:38.88.188.18 3105: 3102: 3099: 3080: 3072: 3069: 3026: 3017: 2998: 2995:Single-Taped 2958: 2955: 2952: 2946: 2915:— Preceding 2876: 2856: 2818: 2813: 2809: 2804: 2800: 2769: 2747: 2736: 2733: 2729: 2726: 2716: 2713: 2704: 2702: 2673: 2670: 2664: 2657: 2652: 2647:while(true) 2645: 2617: 2610: 2579: 2575: 2574: 2562:67.85.81.211 2552: 2526: 2523: 2520: 2500: 2484:68.39.161.88 2482: 2478: 2465: 2394: 2377:202.10.86.59 2368: 2290: 2275: 2269: 2214: 2182: 2179: 2142:ScaledLizard 2130:ScaledLizard 2102:ScaledLizard 2100: 2093: 2090: 2086: 2072: 2061: 2041:87.79.90.204 2035:— Preceding 1959: 1955: 1951: 1938: 1927: 1924: 1898: 1874: 1835:— Preceding 1831: 1827: 1823: 1808: 1786: 1785: 1782: 1762: 1743: 1742:if it sells 1739: 1735: 1731: 1707: 1692: 1617: 1584: 1580: 1544: 1542: 1529: 1527: 1524: 1472: 1451: 1395: 1370: 1348: 1316: 1090: 1086: 1082: 1078: 1042: 1013: 988:Georg_Cantor 984:Peano_axioms 946: 914: 751:it does. -- 748: 723: 714: 711: 698: 691:hypothesized 688: 685: 672: 665:hypothesized 662: 659: 651: 494: 475: 465: 463: 429: 426: 422: 413: 410: 407: 403: 399: 396: 393: 376:Turingproofs 370:— Preceding 367: 363: 360: 356: 352: 349: 340: 336: 333: 324: 294: 290: 281: 268: 264: 248: 235:99.75.50.148 226: 216: 211: 207: 174: 170: 166: 159: 155: 152:universality 151: 147: 143: 132: 128: 124: 117: 116:) is called 109: 89: 85: 81: 77: 73: 60: 43: 37: 3421:consequence 3325:180.174.6.5 3281:180.174.6.5 3083:Deltahedron 3053:Deltahedron 2901:80.7.27.189 2587:—Preceding 2556:—Preceding 2529:—Preceding 2371:—Preceding 2329:68.0.124.33 2009:—Preceding 1965:—Preceding 1710:—Preceding 1699:obfuscation 1504:frequently. 1058:—Preceding 1017:—Preceding 705:thesis and 479:81.57.76.47 301:eventually. 261:hyphenation 229:—Preceding 91:74.194.27.5 36:This is an 3578:SteveBaker 3512:MaxWilderD 3444:Powerpoint 3345:SteveBaker 3301:Guy Harris 3210:incomplete 3048:1253.11003 2981:Cesiumfrog 2886:SteveBaker 2862:Cesiumfrog 2857:sufficient 2835:SteveBaker 2754:SteveBaker 2683:SteveBaker 2623:Cesiumfrog 2504:Cesiumfrog 2447:article.-- 2321:WP:OBVIOUS 2227:wins over 2219:wins over 1935:Definition 1064:66.66.6.25 1023:Rboone2020 770:SineSwiper 587:Cesiumfrog 538:Guy Harris 3508:WP:WEASEL 3423:and what 3315:Brainfuck 3034:. p. 20. 2662:runVM(); 2427:arxiv.org 2262:Mike92591 1703:recursive 1528:The term 997:Chalisque 753:Blainster 686:To this: 450:Chalisque 175:universal 148:universal 61:Archive 1 3454:SIGBOVIK 3333:contribs 3321:unsigned 3277:unsigned 3145:contribs 3137:Fredguth 3133:unsigned 2959:Thanks 2917:unsigned 2770:simulate 2741:and the 2618:simulate 2601:contribs 2589:unsigned 2558:unsigned 2531:unsigned 2497:examples 2434:Egriffin 2397:Egriffin 2373:unsigned 2352:Krischik 2096:Dataflow 2075:Krischik 2068:Ada 2005 2037:unsigned 2011:unsigned 1967:unsigned 1837:unsigned 1712:unsigned 1695:defining 1317:abstract 1060:unsigned 1031:contribs 1019:unsigned 945:and for 695:universe 669:universe 626:Striepan 560:Striepan 519:Striepan 384:contribs 372:unsigned 231:unsigned 70:Untitled 3562:CLEARLY 3450:a paper 3222:neither 3156:Zuse Z3 2949:Problem 2819:require 2185:Invenio 1931:right. 1882:Grumbel 1792:Tgm1024 1674:Likebox 1622:Likebox 1549:Likebox 1506:Likebox 1430:Likebox 1351:Likebox 1279:Likebox 1189:Likebox 1139:Likebox 1116:quoted. 701:in the 675:in the 315:Ruberik 39:archive 3568:WP:NOR 3488:Alegui 3212:, not 3001:KitchM 2659:try { 2449:r.e.s. 2413:r.e.s. 2316:right? 2312:right? 2284:r.e.s. 2282:". -- 2118:Tmdean 1928:cannot 1902:Cesoid 1877:G-code 1770:r.e.s. 1618:finite 1479:r.e.s. 1428:words. 1377:r.e.s. 1324:r.e.s. 1219:r.e.s. 1162:r.e.s. 1120:r.e.s. 1097:r.e.s. 821:Jordan 689:It is 663:It is 285:Mrjeff 195:r.e.s. 179:r.e.s. 3555:: --> 3553:: --> 3551:: --> 3549:: --> 3547:: --> 3545:: --> 3543:: --> 3465:could 3164:that 2947:Minor 2882:WP:OR 2750:WP:OR 2668:.... 2294:Pepve 2251:Pepve 1942:Pepve 1866:stalk 1763:could 1452:daily 1371:after 947:every 915:every 884:Pepve 846:Pepve 438:Pepve 16:< 3582:talk 3516:talk 3492:talk 3476:talk 3452:for 3434:talk 3409:talk 3385:talk 3364:talk 3349:talk 3329:talk 3305:talk 3285:talk 3257:talk 3240:talk 3218:both 3190:talk 3141:talk 3112:talk 3087:talk 3075:"" 3057:talk 3036:ISBN 3005:talk 2985:talk 2965:talk 2925:talk 2905:talk 2890:talk 2866:talk 2839:talk 2810:does 2786:talk 2758:talk 2687:talk 2627:talk 2597:talk 2566:talk 2539:talk 2508:talk 2488:talk 2453:talk 2438:talk 2417:talk 2401:talk 2381:talk 2333:talk 2164:talk 2146:talk 2045:talk 2019:talk 1995:talk 1975:talk 1886:talk 1862:talk 1845:talk 1796:talk 1787:sole 1774:talk 1720:talk 1678:talk 1651:talk 1626:talk 1594:talk 1571:talk 1553:talk 1510:talk 1483:talk 1434:talk 1381:talk 1355:talk 1328:talk 1283:talk 1223:talk 1193:talk 1166:talk 1143:talk 1124:talk 1101:talk 1068:talk 1027:talk 1001:talk 844:. -- 774:talk 749:what 679:and 630:talk 591:talk 564:talk 542:talk 523:talk 505:talk 483:talk 454:talk 380:talk 273:Yaco 239:talk 199:talk 183:talk 173:and 142:(3) 123:(2) 108:(1) 95:talk 3458:may 3297:are 3253:CBM 3226:not 3172:'s 3045:Zbl 2805:and 2782:CBM 2276:not 1960:any 1956:Any 1854:LBA 1776:) 1647:CBM 1590:CBM 1567:CBM 1485:) 1396:are 1383:) 1330:) 1225:) 1187:it. 1168:) 1103:) 709:). 683:). 501:CBM 495:why 341:JC 3584:) 3518:) 3494:) 3478:) 3472:DS 3436:) 3411:) 3387:) 3366:) 3351:) 3335:) 3331:• 3307:) 3287:) 3255:· 3242:) 3234:-- 3192:) 3178:Z3 3147:) 3143:• 3114:) 3089:) 3078:. 3059:) 3043:. 3030:. 3007:) 2987:) 2967:) 2927:) 2907:) 2892:) 2868:) 2841:) 2814:do 2801:NO 2784:· 2760:) 2689:) 2671:} 2650:; 2629:) 2603:) 2599:• 2568:) 2541:) 2510:) 2490:) 2455:) 2440:) 2432:-- 2419:) 2411:-- 2403:) 2383:) 2350:-- 2335:) 2327:-- 2231:. 2166:) 2148:) 2073:-- 2047:) 2021:) 1997:) 1977:) 1888:) 1868:) 1864:| 1847:) 1798:) 1768:— 1722:) 1680:) 1649:· 1628:) 1592:· 1569:· 1555:) 1512:) 1477:— 1436:) 1375:— 1357:) 1322:— 1285:) 1195:) 1145:) 1126:) 1118:-- 1095:— 1093:. 1077:A 1070:) 1051:." 1033:) 1029:• 1003:) 959:∈ 928:⊆ 776:) 632:) 620:, 593:) 566:) 544:) 525:) 503:· 485:) 456:) 386:) 382:• 354:" 241:) 201:) 185:) 169:, 139:.) 97:) 3580:( 3514:( 3490:( 3474:( 3432:( 3407:( 3383:( 3362:( 3347:( 3327:( 3303:( 3283:( 3259:) 3251:( 3238:( 3188:( 3139:( 3110:( 3085:( 3055:( 3050:. 3003:( 2983:( 2963:( 2923:( 2903:( 2888:( 2864:( 2837:( 2788:) 2780:( 2756:( 2685:( 2640:a 2625:( 2595:( 2564:( 2537:( 2506:( 2486:( 2451:( 2436:( 2415:( 2399:( 2379:( 2331:( 2162:( 2144:( 2043:( 2017:( 1993:( 1973:( 1952:a 1884:( 1860:( 1843:( 1794:( 1772:( 1718:( 1676:( 1653:) 1645:( 1624:( 1596:) 1588:( 1573:) 1565:( 1551:( 1508:( 1481:( 1432:( 1379:( 1353:( 1326:( 1281:( 1221:( 1191:( 1164:( 1141:( 1122:( 1099:( 1066:( 1025:( 999:( 976:. 963:N 956:x 932:N 925:S 772:( 628:( 589:( 562:( 540:( 521:( 507:) 499:( 481:( 452:( 378:( 237:( 197:( 181:( 93:( 50:.

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index