Indeterminacy in computation: Difference between revisions

Revision as of 20:47, 6 June 2009

Latest revision as of 22:33, 16 August 2024

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Broad-concept article}}

'''Indeterminancy in computation''' may refer to:

'''Indeterminacy''' is a property of [[formal system]]s that evolve in time (often conceptualized as a [[computation]]), in which complete information about the ''internal'' state of the system at some point in time admits multiple future trajectories.

* [[Quantum indeterminacy]] in [[quantum computer]]s

* [[Nondeterministic finite state machine]]s

In simpler terms, if such a system is returned to the same initial condition—or two identical copies of the system are started at the same time—they won't with certainty produce the same behaviour, as some element of chance is able to enter the system from outside its formal specification.

* [[Nondeterministic algorithm]]

In some cases the indeterminacy arises from the laws of [[physics]], in other cases it leaks in from the [[abstract model]], and sometimes the model includes an explicit source of indeterminacy, as with deliberately [[randomized algorithm]]s, for the benefits that this provides.

==Disambiguation==

'''IndeterminancyIndeterminacy in computation''' may refer to:

* [[Quantumquantum indeterminacy]] in [[quantum computer]]scomputers

* [[nondeterministic finite automata]]

* [[Nondeterministicnondeterministic algorithm]]

In '''concurrency''':

* [[Indeterminacyindeterminacy in concurrent computation]]

* [[Unboundedunbounded nondeterminism]]

{{disambigdisambiguation}}