Talk:Indeterminacy in concurrent computation

From Wikipedia, the free encyclopedia

Contents

[edit] Article for deletion?

I dunno, this article just sounds plain old confused and wrong to me; I'm tempted to suggest deletion. Arguing that a hung gate is a form of quantum indeterminacy is certainly a novel idea, but I think a whole lotta work would need to be done to prove this, in particular, ruling out purely classical explanations like ground bounce and what not. I doubt that anyone who actually designs real transistors for a living would agree with such an assessment. I'd need to see something other than handwaving to believe this. linas 04:19, 16 September 2005 (UTC)

[edit] Disputed statement

I don't believe this:

Arbiters are designed to resolve this instability as rapidly as possible into a stable state, a process known as quantum decoherence

For many reasons. Resolution into stability is not decoherence. Metastability might theoretically be a result of superposition of states, but I have seen no evidence for this in practice.

See International Journal of Modern Physics C

Can Quantum Synchronizers Solve the Metastability Problem of Asynchronous Digital Systems?, Vol. 1, No. 4 (1990) 329-342. Reinhard Männer

Abstract:

The synchronization of asynchronous signals can lead to metastable behavior and malfunction of digital circuits. It is believed — but not proved — that metastability principally cannot be avoided. Confusion exists about its practical importance. This paper shows that metastable behavior can be avoided by usage of quantum synchronizers in principle, but not in practice, and that conventional synchronizers unavoidably show metastable behavior in principle, but not in practice, if properly designed

--CSTAR 20:57, 27 September 2005 (UTC)

This is indeed curious. First of all the above abstract talks about synchronizers instead of arbiters. Does the article explain the difference? Not much confusion exists about the practical importance of metastability for arbiters. Conventional arbiters unavoidably show metastable behavior in principle and also in practice, if properly designed. The metastability of properly designed arbiters has been measured and well qualified many times in the literature. Is this article informed about the literature? Has anyone ever cited this article? Thanks,--Carl Hewitt 21:09, 4 October 2005 (UTC)

Indeterminacy seems to be suggested by Godel's proof that mathematical systems cannot prove themselves. This occurs in practice where diagnosis of a failing machine is extremely difficult without an external system of test intruments. And the nature of information being entropy, a purely statistical measure, suggests that one of the reasons computer software fails particularly when it is very large programs, is that the meaning of one bit in the context of the whole must be close to perfectly consistent with the whole when the whole system exists in a thermodynamic environment in which entropy is also an important measure. Seems best to leave the article simply described as controversial. —The preceding unsigned comment was added by 67.136.147.134 (talk • contribs) 04:41, 1 July, 2006 (UTC)

[edit] POV label

I slapped the POV label on this article for the following reasons:

  1. This article appears to be about quantum indeterminacy in electronic circuits, and not in computation in general.
  2. This article fails to mention competing theories for the cause of that indeterminacy.
  3. This article fails to mention the experimental status of the various competing theories.
  4. The references given appear to have nothing to do with the actual subject of the article.

Please note that this very same issue has already been argued on the talk page to metastability in electronics, which has now been moved to arbiter (electronics) (that is, see Talk:arbiter (electronics).) linas 14:25, 19 October 2005 (UTC)

[edit] Further editing needed

Some further editing is needed. The introduction doesn't say what indeterminacy is, nor where to find out what it is.

The second paragraph is garbled. I'm sorry I don't understand these sentences:

For example Arbiters can be used in the implementation of the arrival ordering of an Actor which are subject to indeterminacy in the arrival order. Therefore mathematical logic can not implement concurrent computation in open systems because of the impossibility of deducing arrival orderings since they are indeterminate. Note that although mathematical logic cannot implement general concurrency it can implement some special cases of current computation, e.g., sequential computation and some kinds of parallel computation including the lambda calculus.
  • There is something wrong with the first sentence: is it Arbiters are subject to indeterminacy or arrival orderings are subject to indeterminacy or actors are subject to indeterminacy?
In the last two cases, it should say "is subject to".
  • deducing arrival orderings --- from what?
Thanks .--CSTAR 02:05, 27 November 2005 (UTC)
Dear CSTAR,
Thanks for noticing these problems. I have attempted some corrections. Please see what you think.
Regards,--Carl Hewitt 02:17, 27 November 2005 (UTC)
But it still doesn't say from what the arrival orderings can or cannot be deduced. From the "transmission orderings?"--CSTAR 02:43, 27 November 2005 (UTC)
It says that the arrival orderings cannot be deduced by mathematical logic.--Carl Hewitt 02:51, 27 November 2005 (UTC)
ARe you saying that the arrival orderings aren't logical truths? --CSTAR 02:54, 27 November 2005 (UTC)
The usual meaning of logical truths in mathematical logic is that they are tautologies.--Carl Hewitt 03:01, 27 November 2005 (UTC)
I'm sorry, perhaps I wasn't clear enough. Let me repeat the question: Is the intended meaning of the statement in the article, the assertion that the arrival orderings (expressed as relations between events) are not tautologies? Why should one ever expect them to be tautologies? Thanks --CSTAR 03:12, 27 November 2005 (UTC)
I clarified the article to say that the limitation is that mathematical logic cannot in general deduce arrival orderings from prior information.--Carl Hewitt 03:18, 27 November 2005 (UTC)
That's an improvement; Perhaps it should begin by saying that since the arrival orderings are indeterminate, they cannot be deduced from prior information by mathematical logic alone. Therefore mathematical logic ....
Excellent suggestion! I have so changed the article. Thanks! --Carl Hewitt 03:44, 27 November 2005 (UTC)

[edit] Merged in Actor model, mathematical logic, and physics

I merged in Actor model, mathematical logic, and physics as per discussion pages.--Carl Hewitt 23:16, 26 November 2005 (UTC)

[edit] Disputed

Here we go again. I'm not saying that mathematical logic can predict the outcome of a calculation, because of the indeterminacy, but it can determine a set of possible computations, and potentially verify that any terminating calculation solves the desired problem. Arthur Rubin | (talk) 02:37, 2 December 2005 (UTC)

The article says
What does the mathematical theory of Actors have to say about this? A closed system is defined to be one which does not communicate with the outside. Actor model theory provides the means to characterize all the possible computations of a closed Actor system. So mathematical logic can characterize (as opposed to implement) all the possible computations of a closed Actor system. However, this is impossible for an open Actor system S in which the addresses of outside Actors are passed into S in the middle of computations so that S can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to S using addresses supplied to them by S.
Regards, --Carl Hewitt 04:35, 2 December 2005 (UTC)
(It looks as if I put the tag in the wrong place. Perhaps the next sentence.) This argument applies to any system with (asynchronous) external inputs, not because of indeterminacy, but because the external inputs are not modeled. As for "implement", see Non-deterministic Turing machine. Arthur Rubin | (talk) 17:41, 2 December 2005 (UTC)
I'm sorry. I don't quite understand the import of the above comment. Regards,--Carl Hewitt 01:34, 4 December 2005 (UTC)
The argument (What does the mathematical theory of Actors have to say about this? ...) applies to any system with external inputs. It has nothing to do with indeterminacy.) Arthur Rubin | (talk) 17:39, 5 December 2005 (UTC)
Thanks. I clarified the discuussion of open systems. Please see what you think. Thanks,--Carl Hewitt 21:45, 5 December 2005 (UTC)
I understand the argument, now. (Please merge the duplicate paragraphs.) It's still not due to what I would call "indeterminacy", but due to the structure of the external interface. In other words -- any system with asynchronus external inputs cannot be simply modeled by logic or "traditional" computation theory. It doesn't have anything to do with "indeterminacy", quantum effects, relativistic light cones, or anything else you've combined with it in the past. If you want to further ambiguate indeterminacy, go right ahead -- but that's what you'll need to do for me to remove the *disputed* tag. Arthur Rubin | (talk) 22:32, 6 December 2005 (UTC)
Thanks for your comments. I have further clarified the article. Please see what you think. Thanks,--Carl Hewitt 23:07, 6 December 2005 (UTC)

[edit] Kinds of indeterminacy

Quantum indeterminacy is usually mentioned when one is concerned with the predictability or nonpredictability of events. For example, predictability explicitly arises in the earlier physical theory now known as classical mechanics, which lead to a philosophical position of Scientific determinism. Some philosophers have tried to identify the basic types of indeterminacy that underly the inability of humans to predict the future. Four types of indeterminacy are:

  • quantum indeterminacy, built into the structure of physical reality.
  • indeterminacy due to chaos as described in chaos theory ("Sensitive dependence on initial conditions").
  • indeterminacy caused by limited powers of observation and integration of the facts.
  • limitations due to the nature of human memory and thought processes. —The preceding unsigned comment was added by 24.23.213.158 (talk • contribs) 22:36, 28 February 2006 (UTC)
I'm not sure what you're referring to, but my assertion is that the system described is not predictable because of external inputs, not because of "quantum indeterminacy", or any other kind of indeterminacy. Arthur Rubin | (talk) 02:24, 1 March 2006 (UTC)
The consensus in the scientific literature is that outcome of the operation of an Arbiter is indeterminate once it has become metastable. Do you know of any literature to the contrary? —The preceding unsigned comment was added by 24.23.213.158 (talk • contribs) 05:22, 1 March 2006 (UTC)
Hello Carl (welcome back!) ;) --CSTAR 05:55, 1 March 2006 (UTC)
The consensus in your writings is such -- I have doubts about the scientific literature in general. But that has nothing to do with my assertion -- the nonpredictability is not due to indeterminancy, but due to external inputs. -- Arthur Rubin | (talk) 17:42, 1 March 2006 (UTC)
The citations in Arbiter (electronics) support the view that Arbiters once they have gone metastable have indeterminate behavior. Do you have any references to back up your personal view? —The preceding unsigned comment was added by 24.23.213.158 (talk • contribs) 23:09, 1 March 2006 (UTC)
The article Arbiter (electronics) supports my view. "Even synchronous computers need Arbiters to deal with input from outside the clock domain of the central processing unit: from keyboards, networks, disks, etc. " It's the external input which causes the nonpredictability, with Arbiters partially mitigating that unpredictablitility. Arthur Rubin | (talk) 23:16, 1 March 2006 (UTC)
It is not the external input which cause the indeterminacy. According to the literature, it's the metastability which results in the indeterminate outcomes. Coming from the outside, inputs are unpredictable. If the external inputs cause metastability in an Arbiter then the outcome is indeterminate. —The preceding unsigned comment was added by 24.23.213.158 (talk • contribs) 05:41, 2 March 2006 (UTC)
The nonpredictability is called by outside inputs. You're the one calling it "indeterminacy" in this context. (Oh, and sign your comments. It's a separate violation of Wikipedia conventions, in addition to the violation if you edited any of the articles related to your research. — Arthur Rubin | (talk) 07:24, 2 March 2006 (UTC)
So it seems that you do not have any references to support your personal views on this matter? Is there not a Wikipedia policy against insisting on pushing your personal research point of view?
My browser says "You are not logged in. Your IP address will be recorded in this page's edit history."
—Preceding unsigned comment added by 24.23.213.158 (talk • contribs) 08:13, March 2, 2006
Back to one ":", or we're going to find ourselves all the way across the page.
Your references and the articles you wrote do not support your theory that the nonpredictability is caused by indeterminacy. If you couldn't demonstrate it, it probable isn't supportable.
As for signing -- your IP address is recorded in the history, but you still should record it on the talk page by ending your comments with "~~~~". — Arthur Rubin | (talk) 08:18, 2 March 2006 (UTC)
The references in Arbiter (electronics) support the thesis that the outcome of an Arbiter is indeterminate once it becomes metastable. Note that there are several different kinds of indeterminacy from Talk:Indeterminacy in computation#Kinds of indeterminacy above.
By your response you have confirmed that you do not have any references to support your personal views on this matter. This is against Wikipedia policy on pushing your personal research point of view. Anonymouser 08:29, 2 March 2006 (UTC)
Apparantly you're too close to the issue, and are not allowed to edit the article in question, Carl. I'm willing to submit the issue of whether you've established your point and whether I've established mine to peer review -- remembering that it's our peers on Wikipedia rather than your peers in theoretical computation theory nor mine in mathematical logic. — Arthur Rubin | (talk) 15:57, 2 March 2006 (UTC)
Please see Wikipedia talk:Requests for arbitration/Carl Hewitt/Workshop#The use of indeterminacy for an extended discussion of indeterminacy in arbiters, including a variety of references. --Allan McInnes (talk) 02:16, 8 March 2006 (UTC)

Has anyone thought that the indeterminacy is due to noise once the arbiter becomes metastable? 24.23.213.158 23:03, 2 March 2006 (UTC)

The noise argument looks very strong. If the inputs are the same within the noise bands, then what is the argument that the outcome depends on the input? Doesn't the outcome depend on the noise in the arbiter? —The preceding unsigned comment was added by 67.134.140.2 (talk • contribs) 09:12, 8 March 2006 (UTC)