Talk:Indeterminacy in concurrent computation

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)

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)

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)

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)

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)

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)

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)

---

Introduction line

Currently reads "Indeterminacy in concurrent computation is concerned with the effects of indeterminacy in concurrent computation" - so it's concerned with the effects of itself, nice. Surely someone can think of a better intro than that. 82.39.140.240 (talk) 22:36, 1 June 2009 (UTC)

The line actually reads as follows: "Indeterminacy in concurrent computation is concerned with the effects of indeterminacy in concurrent computation." where the links provide additional meaning. But you are right that we should word it better.67.169.49.29 (talk) 14:45, 2 June 2009 (UTC)

Sense and nonsense

I'm sorry to be frank, but this section is nonsensical:

Prolog-like concurrent systems were claimed to be based on mathematical logic

Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog-like concurrent message passing systems using unification of shared variables and data structure streams for messages. Claims were made that these systems were based on mathematical logic.[citation needed] This kind of system was used as the basis of the Japanese Fifth Generation Project (ICOT).

Carl Hewitt and Gul Agha [1991] argued that these Prolog-like concurrent systems were neither deductive nor logical: like the Actor model, the Prolog-like concurrent systems were based on message passing and consequently were subject to the same indeterminacy.

The mathematical properties of a formal system has *nothing* to do with the physical implementations of it. One can formalize a programming language using a multitude of mathematical tools (such as, er, a logic..), but this unfortunately does not affect its physical realization.

To be clear: prolog *was* formalized (see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.954 and its citations). This is a mathematical, abstract property, that *does not affect* the indeterminacy a physical system that implements prolog might have (other than the semantics of the language itself).

(Also, please note that many languages has been formalized with some 'logic', even the ones that does not favor the 'logic programming' paradigm) --187.40.172.119 (talk) 03:25, 20 August 2010 (UTC)

The hard part is formalizing concurrency. The formalization of ISO Prolog does not have any concurency. The physical indeterminacy of hardware used in the implementation of concurrent programming languages results in indeterminacy in the behavior of programs. It is well known that concurent programs cannot be reduced to pure logic (see Common sense for concurrency and inconsistency tolerance using Direct Logic(TM) and the Actor Model). 64.134.238.26 (talk) 20:54, 20 August 2010 (UTC)

Indeterminacy definition is looped

The word "indeterminacy" is linked to some pages - which bring you back to here! — Preceding unsigned comment added by 142.167.186.3 (talk) 01:17, 29 May 2012 (UTC)

Recommend this Article be Deleted

This article reads as if it were written by someone related to Carl Hewitt who is apparently on probation at Wikipedia. The text is mainly focused on the Actor model and Logic Programming, there is very little about the general topic. When I googled " Indeterminacy in concurrent computation" on 16 April 2013, the hits I found on the first few pages of results seemed to be either directly derived from this article, or in recent articles by Carl Hewitt himself. Hence, I don't believe that Indeterminacy in concurrent computation is a worthy topic for Wikipedia. Just to double check, I just googled "indeterminacy"+"concurrent computation", even when the two phrases are separated all the hits on the first few pages seemed to be derived from this article or the recent works of Carl Hewitt. Pmokeefe (talk) 17:35, 16 April 2013 (UTC)

Merge to Carl Hewitt? It might still be notable, even if it's his entirely his not-entirely-accepted theory. — Arthur Rubin (talk) 22:02, 16 April 2013 (UTC)

I deprodded because at first glance, there are references independent of Hewitt. Merge sounds like a good idea if these independent refs turn out to be bogus. Feel free to bring this to AfD if notability is a concern. But non-neutrality of the prose by itself is a cause for editing and balancing, not deletion, if the sources are there to improve it. --Mark viking (talk) 22:19, 16 April 2013 (UTC)

But what is written here is incoherent. I can't even figure out the point that is trying to be made here. There are a variety of theories in comp sci that describe non-determinism; none I know of are mentioned here. For example, the history monoid and the trace monoid explicitly describe non-determinism as the commuting portions of communicating systems. What the heck does the stuff here have to do with that, or, e.g. the calculus of communicating systems (CCS)? Or any of the text-book notions of reduction and confluence (computer science), which is how non-determinism is normally talked about? No one has re-rewritten or improved this article in 11 years, because no one can even figure out where to start, aside from deleting it entirely, and starting from scratch? Sorry to be so harsh, but I've read the text three times, and I can't quite figure out what it's trying to say.

For example, lets look at the first three sentences of the current article:

Patrick Hayes [1973] argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading". Robert Kowalski developed the thesis that computation could be subsumed by deduction and quoted with approval "Computation is controlled deduction." which he attributed to Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes, Carl Hewitt claimed that logical deduction was incapable of carrying out concurrent computation in open systems[citation needed].

The first two sentences seem to suggest that Hayes, Kowalski were ignorant of the Curry-Howard correspondence ?? Maybe in 1973, this was still an obscure, unknown thing? Or does "processes of computation and deduction" mean something else? WTF does this sentence even mean? Third sentence: "logical deduction was incapable of carrying out concurrent computation in open systems" Huh??? Does he mean that logic cannot be used to reason about open systems? Is this some arcane statement about Kripke semantics? What does this sentence refer to? what does it mean? OK, so next paragraph:

Hewitt [1985] and Agha [1991], and other published work argued that mathematical models of concurrency did not determine particular concurrent computations

First reaction is: no-shit, sherlock, indeterminancy is a fundamental property of concurrent computation, and this would have been equally "obvious" by 1985 and 1991, so surely Hewitt and Agha are saying something more subtle than that. So it seems that sentence can be discarded, or re-written.. Next sentence: "The Actor model makes use of arbitration ..." but non-determinism is not specific to the actor model. Its made explicit in notions such as confluence, or the partially-commutative monoids, in general. So can we delete "Actor" from that paragraph? If this is done, what's left doesn't seem to say anything .. noteworthy.

Then we move onto this sentence: Therefore mathematical logic can not implement concurrent computation in open systems. Huh? Mathematical logic, here, refers to what? Propositional logic? predicate logic? First-order logic? Higher order logic? Topoi? type theory? Is it trying to say that CCS and monoids and term rewriting aren't "mathematical logic"? What does the word "implement" mean? Does it mean "isomorphic" or "homomorphic"? Does it mean elementary extension? Does it mean something else? The trace monoids do provide a language for talking about homomorphisms of systems of concurrent computation; at least some of what model theory does has been extended to concurrent systems, its used in semiconductor design these days (boolean SAT and SMT solvers). So WTF? Can we scratch this sentence? One can proceed through this entire article, and tag it with dubious-discuss tags on every single sentence. I'd re-write this myself, except I can't figure out what the article is supposed to be about. 67.198.37.16 (talk) 04:27, 20 January 2017 (UTC)

AfD candidate surely (or prompt rescue project)

Uh, someone knowledgeable needs to decide whether it's tendentious overreach to motivate an entire typology of concurrent computation on the seldom-observed Buridan's ass (see specifically Buridan's Principle) and then this article needs to be made comprehensible in a proper Wikipedia idiom, or it needs to die in a fire, with no in between. — MaxEnt 22:58, 22 February 2016 (UTC)

The irony is, of course, that this article is stuck in a meta-stable state between re-writing and deletion. Maybe, like Schroedinger's cat, it's both dead and alive.67.198.37.16 (talk) 05:24, 20 January 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Indeterminacy in concurrent computation. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20171210124010/https://vvvvw.aaai.org/Papers/Symposia/Spring/2006/SS-06-08/SS06-08-003.pdf to https://vvvvw.aaai.org/Papers/Symposia/Spring/2006/SS-06-08/SS06-08-003.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 02:48, 9 January 2018 (UTC)