Content deleted Content added
Universal Turing Machines |
|||
Line 253:
:The text appears almost identical to the contribution to [http://groups.google.com/group/comp.theory/browse_thread/thread/97be4cfe4eb1821e] by Marissa Kay on Thurs, Feb 9 2006 7:48 -- [[User:PJTraill|PJTraill]] 01:11, 19 February 2006 (UTC)
::Both had the same author. The article, itself, clearly stands on its own since the arguments made in it are sufficiently self-contained and cogent to settle the issue, subsuming prior published literature on the matter, particularly in its taking into account the finiteness imposed as a result of the Bekenstein Bound, which has been neglected in the literature and is really the critical point in deciding the issue. The question of whether the universe is deterministic or not is open. The Schroedinger equation is, in fact, deterministic and state evolution under it, likewise so. Whether the apparent non-determinism associated with "collapse" is real or only epiphenonemal and deriveable from a more fundamental, and deterministic, substrate (e.g. by decoherence, consistent histories, or some other mechanism, etc.) is really the central issue of the so-called [[measurement problem]] of quantum theory and is as-of-yet unresolved. But, the question is moot anyway: non-deterministic FSM's are <i>not</i> equivalent to deterministic FSM's! This equivalence only applies to deterministic vs. non-deterministic FSA's. The non-equivalence for FSM's is readily seen by the trivial counter-example of a FSM with states {S,F}, input {X}, outputs {Y,Z}, start state S, final state F and the two transitions on input X from S to F, one transition having output Y, the other having output Z. A deterministic FSM cannot yield more than one translation for any input. This one yields the two translations for the input "X": "Y" and "Z". Therefore it is not reducible to an equivalent deterministic FSM.
== Universal Turing Machines ==
| |||