Talk:Turing completeness
This is the talk page for discussing improvements to the Turing completeness article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1 |
{{WikiProject banner shell}}
to this page and add the quality rating to that template instead of this project banner. See WP:PIQA for details.![]() | Mathematics C‑class Mid‑priority | |||||||||
|
{{WikiProject banner shell}}
to this page and add the quality rating to that template instead of this project banner. See WP:PIQA for details.![]() | Computer science C‑class Top‑importance | ||||||||||||||||
|
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: , where is the blank symbol.
- those that only read or write the symbols: .
- 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 as strings over such that for all TMs in the second set, computing some partial function on the strings over , 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)
- A simple example:
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 ()? 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)