Talk:Turing completeness

HTML5 + CSS3

They are not Turing complete together. The provided source is just a blog post and a piece of software. There are no e.g. peer reviewed articles claiming the same. As far as I understand the software does not work automatically, but it requires the user to click on some elements on the page. So the execution model requires a separate component which is either a user or e.g. a small piece of JavaScript which performs the clicks. It means it should not be considered Turing complete alone, without including that "clicking" element, whatever it is. So it's not only HTML5 + CSS3, but HTML5 + CSS3 + something that is able to detect elements which are to be clicked and click on them.

For this reason I marked it as dubious.123unoduetre (talk) 15:47, 25 April 2020 (UTC)

The blog says the following:

Finally, a finite, predetermined sequence of mouse and key events are applied to the DOM, updating :focus, :target, :checked CSS pseudo-classes.

123unoduetre (talk) 16:07, 25 April 2020 (UTC)

I don't see any comments about it here, so I will remove the reference to HTML5 + CSS3 from the page.123unoduetre (talk) 15:42, 29 April 2020 (UTC)

"Turing complete" vs. "computationally universal"

In my experience "computationally universal" is the term that has priority and is used in the academic literature; e.g. the google n-gram viewer shows no hits for "Turing complete" but lots of them for "computationally universal". I have no idea who invented "Turing complete" and an article like this would be improved by a reference to its first use. I think "Turing complete" is illegitimate and the n-gram result is reason enough to change the name of the article to "Computationally universal". I am apparently going against the tide but does anyone agree with me? (I see I am sort of echoing a part of what is in the 'Untitled' section above.) --Jar354 (talk) 17:04, 27 April 2020 (UTC)

In Scholar Google, which is the reference searching engine for academic subjects, I got 2,130 hits for "computationally universal", and 16,800 for "Turing complete". However, such counts do not matter here, as the two terms are not at all synonymous: "computationally universal" is either a vague notion that does not have any workable definition, or it refers implicitely to the Church–Turing thesis. In both cases, "computational universality" cannot be proved. On the other hand, Turing completeness can be mathematically proved, and proofs of Turing completeness support Church–Turing thesis. So, the article is definitively about Turing completeness. In the article, the two terms are presented as synonymous. IMO, this is an error that must be corrected. D.Lazard (talk) 17:49, 27 April 2020 (UTC)

"Illegitimate" is an amazing thing to say, and I'd suggest you redact it. As for 'priority', Alonzo Church used "Turing-complete" in 1957, and if you're not thrilled with how he used it there, the Symposia on Theory of Computing were using it in the 1970s. I don't understand how you got no hits for 'Turing complete' on the Ngram viewer - I get a lot of hits for it - but it's a flawed tool either way. DS (talk) 18:01, 27 April 2020 (UTC)

Interesting and thanks for your attention. (I wonder why I didn't get notification of your comment? Thought I was watching.) I didn't see that N-gram is case sensitive, very sorry. Also this is showing my age. A comparison shows Turing complete passes computationally universal only in 1999, decades after I studied this stuff. Now that you point out that the two are not synonymous I accept the newer word better. I still don't like it (we're not talking about equivalence to Alan Turing, but rather to his UTM) but I admit my taste is probably not relevant. A citation in the main article would still be helpful. --Jar354 (talk) 13:17, 28 April 2020 (UTC)

Unfortunately, I am unable to provide a source. It is for this reason that I have put "IMO" in my previous post, and I have not edited the article. My feeling is that the popularization of the term "Turing complete" is a consequence of the fact that calculability theory and computational complexity theory have more or less fusioned (after all the worst complexity is to be not computable), and that "complete" is widely used in complexity theory, with a similar meaning (for example NP complete) (in fact it is more the methods of proof that are similar than the meanings themselves). D.Lazard (talk) 14:03, 28 April 2020 (UTC)

I'm curious about the wording "a universal computer is defined as 'a device with a Turing-complete instruction set'". I have not been able to find any precise definition of "Turing-complete instruction set", and in particular I don't see it within Wikipedia. There seems to be (IMO) some incompleteness or circular logic here, but I don't think this qualifies as an 'issue'; so I'm placing it here rather than under "Issues". Lacking that definition (if it truly is lacking and not simply on oversight on my part), then it seems that the article relies on the idea that whatever the "instruction set" of a given computational model is, it is deemed "Turing-complete" if it is possible to simulate a TM with the model and vice versa. I don't have a problem with that; I just think it would be good to either offer some more precise/authoritative definition of "Turing-complete instruction set" or modify that wording accordingly. Mike-c-in-mv (talk) 21:28, 8 May 2023 (UTC)

On second thought, I realize now that it is not necessary to modify this section because it is under the heading "Non-mathematical usage". So my previous concern about being more "precise/authoritative does not really apply. The way it is now is adequate for this context. Please excuse me.

Mike-c-in-mv (talk) 15:18, 22 May 2023 (UTC)

Simplification?

Would it be valid to say that a system is Turing-complete if it can be used to replicate all of the basic elements of computation? And that such a system can — in principle, given sufficient time and resources — be used to reproduce any and all computer programs? DS (talk) 05:53, 2 March 2021 (UTC)

That would be a bit misleading. Computer programs can do such things as send email, receive email, act as an answering machine, run Wikipedia, run Minecraft, operate a robot, or handle money transfers. Turing machines can do none of those things.

The computer programs themselves don't really do all of this; they interact with peripheral equipment such as memory devices, displays, network equipment, etcetera, which in turn interact with their environment and other devices, and it's the whole system that implements these things. The computer programs just act to control them.

However, they are not the only things that control them, and in order to exert their control, they perform all kinds of sophisticated interaction with these devices. Interaction does not consist of computation alone; for instance, timing aspects are often very important. So what computer programs do is more than just computation. Rp (talk) 22:40, 9 November 2022 (UTC)

I agree with the intent of this statement, but I am not sure that "the basic elements of computation" is well defined. Formally, the "basic elements" of different computational models differ quite widely. E.g., Turing Machines, the RAM model, lambda calculus, unrestricted rewriting systems, combinators, circuits, ... And informally, there is even wider variation.

Mike-c-in-mv (talk) 18:49, 15 May 2023 (UTC)

Some issues

The present text has some issues.

One is that it remains vague about what it means for a machine or mechanism to simulate another. This should be explained. In particular, it should be explained what it means for one computational mechanism to simulate another, even when the domains are different.

Another thing worth explaining is that a mechanism can be Turing-complete (universal) and yet less computationally powerful than another mechanism, because Turing completeness does not imply the ability to express arbitrary computable functions on the mechanism's own domain. For instance, [Conway's Game of Life] being universal just means that when turned loose on particular configurations of cells, the Game of Life simulates a certain other Turing-complete mechanism (e.g. Turing machines), but it doesn't imply that the game is able to express arbitrary computable functions on configurations of cells, and there may well exist another game that is strictly more powerful than the Game of Life in that sense.

Finally, the History section has some inaccuracies:

• It is not the case that every real-world design for a computing device can be simulated by a universal Turing machine. Computing devices do a lot more than compute computable functions, and designs have purposes besides expressive power. This should be reworded to be about the ability to calculate functions on discrete domains.
• Babbage's engine arguably wouldn't have been the first Turing-complete machine, because programs had to make do with a fixed amount of working memory; but perhaps its input "language" was universal, if it assumed no such limitation. In general, there should probably be a clearer discussion about loose ways in which the term Turing completeness is used even when the amount of working space is bounded.

Rp (talk) 22:11, 10 November 2022 (UTC)

I'm not sure I understand the statement "...a mechanism can be Turing-complete (universal) and yet less computationally powerful than another mechanism...". It would be helpful if you, https://en.wikipedia.org/wiki/User:Rp (or anyone else who would like to weigh-in), could please provide an example of a Turing Complete computational mechanism that is more powerful than a Turing Machine. Perhaps In particular, I don't see how John Horton Conway's Turing Complete Game of Life is such an example. As noted here in Wikipedia, the Game of Life has been shown to be capable of simulating any given Turing Machine. And given a suitable encoding, a Turing Machine can be devised that simulates the game for any given initial configuration. Hence, the game and the TM model can simulate each other and are therefore exactly equal in computational power.

So perhaps I'm not understanding what is meant by "mechanism" in the statement quoted above. Or, perhaps the point of misunderstanding has to do with the phrase "on the mechanism's own domain". Every approach to Computability Theory that I'm familiar with assumes that the instance of the computation to be done is encoded in some manner appropriate for the computational model in question. That is why I added "Given a suitable encoding" to my response.

One thing I think we can both agree on is when you said "Another thing worth explaining is...". I.e., this article is good, but I believe we can make it better by being more clear, precise, and complete. I aim to help with that, but I wanted to test the waters here in the Talk page before I start editing other people's contributions.

Mike-c-in-mv (talk) 19:14, 15 May 2023 (UTC)

A simple example:

• Deterministic Turing Machines compute partial functions from strings to strings over a certain alphabet.
• Subsets of such TMs compute subsets of these functions; in this sense, they are less powerful.
• However, such subsets may be strictly less powerful and still Turing complete.
• For instance, consider two subsets of DTMs:
  • those that only read or write the symbols: $a,b,\#$, where $\#$ is the blank symbol.
  • those that only read or write the symbols: $a,b,c,\#$.

Clearly, the first set is less powerful than the second, in the above sense.

Yet, it is just as powerful, in the sense that the second set of machines can be simulated by the first set, that is to say, we can encode the strings over $\{a,b,c\}$ as strings over $\{a,b\}$ such that for all TMs in the second set, computing some partial function on the strings over $\{a,b,c\}$, some TM in the first set computes the corresponding function on the encoded strings.

So it is important to distinguish two properties:

• the ability to compute all (computable) partial functions over a given domain;
• the ability to simulate all computable functions over any domain by computing the corresponding functions over the given domain, according to some mapping of the values of the first domain to values of the given domain.

The first property is stronger than the second; the second is Turing completeness. In practice, people sometimes use Turing completeness to refer to the first property.

Rp (talk) 22:23, 18 May 2023 (UTC)

I see, thank you. So the idea that the point of misunderstanding or difference of interpretation does indeed center around considering encodings for different domains. I also agree that the second interpretation above is (in my experience) much more common in the context of computability theory (as opposed to sometimes in practice). In that case, I agree with this part of the Talk thread, and so I will not attempt to 'improve' the actual article, since it does not need improvement in this area.

Thanks again for the clarification here.

Mike-c-in-mv (talk) 01:03, 22 May 2023 (UTC)

Create list of unintentionally turing complete software?

There's a list of unintentionally turing complete software, and it's already pretty long and I'm fairly certain it's quite incomplete. Is it worth creating a list article for it? romir.k (talk) 02:03, 8 August 2023 (UTC)

Infinite physical memory can happen

In this wikipedia page it says infinite physical memory is not possible. However I have demonstrated recently that a single qubit can represent infinite memory by using the probability coefficient of the qubit state as an analog signal. That is if the qubit state is 1/sqrt(n) (ket(0)) + sqrt(1 - 1/n) (ket(1)) the value n can also be found by measuring the probability the qubit is in the state ket(0) and distinguishing 0's and 1's. The paper is at https://www.researchgate.net/profile/Santosh-Gupta-10. This system can also be used a computer with analog input and digital output. Skgupt (talk) 12:57, 2 December 2023 (UTC)

This is actually a sixth way of representing information (quantum analog-to-digital), the other five ways being classical analog to analog, classical digital to digital, stochastic analog to analog, stochastic digital to digital, and quantum digital to digital (quantum computing). 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 23:18, 4 December 2023 (UTC)

How would you measure normalized amplitude squared ($|\Psi (x,t)|^{2}$)? That's not an observable. -- Shmuel (Seymour J.) Metz Username:Chatul (talk) 18:44, 5 December 2023 (UTC)

Preparing this state, which is not difficult using the Hamiltonian derived in the research paper, or alternatively using a Hamiltonian I derived in a follow-up research paper, and perform a measurement and get 0 or 1. Record this value of 0 or 1. Keep repeating this process, and the probability of 0's will converge to the value 1/n. Hence the normalized amplitude squared is an observable by measuring the probability that measurement of the state results in 0. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 19:15, 5 December 2023 (UTC)

Ofcourse there is still the fact that to look at the answer as a classical numerical value, and supposing the number is very big, one needs a lot of storage space (there is no way around this because the human mind would have no other way of perceiving the number), but the difference is the number can be stored on a single qubit and one can manipulate it, perform arithmetic, etc., whereas on a classical digital computer one can't even store a large enough number in the first place because one runs out the space to store it. So for example, I can store google to the power of google on a single qubit which is impossible on a classical computer due to finite memory, perform arithmetic etc, and I can read out the value using enough measurements though ofcourse to be able to "see" that value one would need a lot of space. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 19:40, 5 December 2023 (UTC)

With an analog computer one can try to prepare the value 1/n but without a sensitive enough detector it would be impossible to confirm what the value is and hence essentially impossible to prepare such a value, and all detectors are limited by the Uncertainty Principle. So infinite physical memory is possible in this sense, though measuring out the value so it can be read may not be a great thing to do in practice. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 19:54, 5 December 2023 (UTC)

Assuming the Copenhagen interpretation for simplicity, wouldn't the first measurement collapse it to an eigenstate of the observable, causing the second measurement to yield the same value? -- Shmuel (Seymour J.) Metz Username:Chatul (talk) 17:27, 6 December 2023 (UTC)

Sorry I should have specified what is being measured, measurement is of the z-component of spin so the value is 0 or 1. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 02:17, 7 December 2023 (UTC)

Also it is assumed that after measurement the state mentioned above is prepared again and measured again to get 0 or 1, or it could be done in ensemble. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 02:19, 7 December 2023 (UTC)

As with any measurement, that leaves it in an eigernstate: |-1/2> or |+1/2>, and repeating the measurement gives the same value. If you prepare the state again then you are no longer measuring the original state. I suspect that you're leaving out critical details of the proposal. -- Shmuel (Seymour J.) Metz Username:Chatul (talk) 10:32, 7 December 2023 (UTC)

I;m sorry but you are not understanding or trying to understand. After measurement along the z-axis the value will be |0> or |1> not |-1/2> or |+1/2> you seem to be talking about measurement along the x-axis or y-axis. The state is prepared again after measurement collapses to one of these two states. There is nothing wrong with that. I'm not talking about repeating the measurement after the state is already collapsed. Then that would give the same value. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 18:34, 7 December 2023 (UTC)

Whoosh! I understood what you wrote perfectly. A measurement of the Z component of electron spin gives a value of plus or minus 1/2; the fact that you used 0 and 1 as labels for associated eigenvectors doesn't change that. If the state is prepared again then a subsequent measurement of the Z component of spin provides no information on the original state. Again, you are clearly leaving out crucial information. -- Shmuel (Seymour J.) Metz Username:Chatul (talk) 12:57, 8 December 2023 (UTC)

Ok let me make it clear. If I prepare the state with 1/sqrt(n) as the coefficient, then perform a measurement along the z-axis, it will collapse to ket(0) with a probability 1/n and ket(1) with a probability 1-1/n. Then I prepare the original state again with 1/sqrt(n) as the coefficient, then perform a measurement along the z-axis, and then again it collapses to ket(0) with probability 1/n and ket(1) with probability 1 - 1/n. This process is repeated until enough 0's and 1's are collected to form a convergent probability that there are 0's, corresponding to 1/n. Anytime the state is prepared and a measurement along the z-axis is performed, I get information about the state since it collapses to 0 and 1 with the probability according to the coefficient of ket(0) of the prepared state. I don't get enough information about the probability until enough experiments are repeated. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 13:12, 8 December 2023 (UTC)

I have a feeling another person is needed because we don't seem to agree even though I am being very clear. 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 13:13, 8 December 2023 (UTC)

The talk pages are for discussing improvements or changes to the article, they are not a forum to discuss the subject or conduct research on it. If you are really interested in having this conversation could the two of you move it to personal correspondence? AquitaneHungerForce (talk) 13:35, 8 December 2023 (UTC)

Ok I have no problem discussing it in person, but I feel that I am right and they are wasting my time and the wikipedia edit should be made, so what should happen for that? 2607:FEA8:E920:B8A:DE30:4434:F77B:FA73 (talk) 13:59, 8 December 2023 (UTC)

Lead paragraph changes

I have two issues with the changes to the first paragraph. The first is exactly WP:ISAWORDFOR, so I won't summarize it here. The other is that it over-emphasizes the colloquial usage outlined in the section Non-mathematical usage. AquitaneHungerForce (talk) 14:19, 14 March 2024 (UTC)

Greetings. Nice to see you here. Vis-a-vis your first concern, recognizing the intention of WP:ISAWORDFOR, the original language IS opaque (and in no way "encyclopedically direct"); and second, "Turing completeness" is a term (for the concept of "Turing completeness"). Thus it is appropriate to initially explain it as such, and develop nuance from there.

Regarding your 2nd, how's this for integrating the aspect of "Turing completeness" you feel is under-emphasized (and recognizing the term is indeed used to apply to all three of these applications:

Turing completeness is a term used in computability theory to designate a computer, programming language, or set of data-manipulation rules capable of simulating a Turing machine, a mathematical model of computation developed by English mathemetician and computer pioneer Alan Turing. A system that is able to recognize or decide other data-manipulation rule sets (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal.

Best, 2601:196:180:DC0:D14C:66F2:D249:FD73 (talk) 14:38, 14 March 2024 (UTC)

I'm not sure I follow your first point. The old section may be opaque, I'm certainly open to changes to make it clearer, but I don't see how the changes do that. I also don't get the distinction you are making between "Turing completeness" as a term and any other word. In the example at WP:ISAWORDFOR, "dog" is also a term (for the concept of "dog"). To me these cases seem analogous.

I think that introducing it as a term operating on computers and programming languages, over-emphasizes the informal way in which it is used. Computers and programming languages have to be idealized and described as models of computation for to talk about their Turing completeness. This usage is covered in the body of the article, and I certainly don't want to expunge it completely, but I feel it creates a false impression when the article leads in with this, and weird dissonance when the next sentence seems to say something that directly contradicts this. I think the old version of the article did an alright job of clearly separating the informal and formal uses.

Lastly, having now read both versions a dozen times, I do feel that explaining that Turing machines are from Alan Turing is probably extraneous in the first paragraph. A neat piece of trivia, but not one of the most important things about the topic. Maybe removing this, or moving it down the page, would help to make things more direct? AquitaneHungerForce (talk) 15:06, 14 March 2024 (UTC)

Clearly we each see this completely oppositely. Wikipedia is intended to be an "everyman's encyclopedia", which "anyone can edit". You are advocating for an over-specialized view of all this (which I could dig a nice linked acronym for out of the MOS, but there's no point). "Touring completeness" is both a term and a concept, a term describing and defining computers, software, and rule sets that simulate Touring machines. (Which of course needs to be (concisely) in the lead, what a "Turing machine" is, high up in it, and inherently gets credited to Turing (as this is not an article in a computer journal where every reader is likely to know all about both). The sooner the better in both cases. Otherwise it's just unnecessary connect the dots and playing Clue to core Wikipedia users (who know nothing about any of this going in).

(And me? Someone who literally was *born* with computers in their life...my father actually being a digital computer pioneer, designing and literally soldering together some of the 1st integrated circuits himself, and later earning several early patents in core memory - which is no WP violating effort at "flashing credentials" to gain an edge in an argument, just context for you to recognize I have one foot in each camp, so to speak. Ending up at this page not researching computers but merely having seen the 1950s romantic comedy Desk Set on Turner Classic Movies last night, and wanting to check something about ENIAC (which was used as the model for the comically exaggerated EMERAC featured in the movie). So, one light leap from TCM to ENIAC, and one curious click from there to here (to figure out just what in heck - in layman's terms - "Turing completeness" meant).)

In a perfect world - Heck, the computer world is filled with "ideal" conditions (like "infinite memory"), why not let it be here too? - it would be helpful for you to clear your head of any preconceptions and rewrite this lead along the revised lines above, making the fewest mincing changes you feel you must. The best way for that to happen - and I truly hope it does, as the encyclopedia is not about either you or I - is for me to step away and trust you entirely with "consensus" and not be a nettle in your side. A consensus which must represent the interests of the average user, not one already fluent in computer science.

Thank you for your civility, efforts to find common ground, and meeting me here to try to. Adieu. 2601:196:180:DC0:D14C:66F2:D249:FD73 (talk) 16:08, 14 March 2024 (UTC)

I don't think we see this all that differently. I definitely don't want this article to be overly technical, and I'm happy to have informal notions used to introduce the topic. The issue that has to be overcome, however is two-fold. First I do think we have to avoid conflating formal and informal notions, and present them as separate but related. I see a lot of students having misconceptions which are made worse by having conflicting definitions for a single concept. The second issue is that it's really hard to write well sourced information on the informal concept. Scholarly sources tend to focus on formalism, because that is their nature, and informal concepts are not always well pinned down.

I still feel like I do not fully understand your reasons for wanting the change. I was hoping thorough discussion could help us reach a better version of this bit. AquitaneHungerForce (talk) 16:42, 14 March 2024 (UTC)