Probabilistic / Nondeterministic Turing Machines

From: Guy Macon (http://www.guymacon.com/)
Date: 01/29/05 

Date: Sat, 29 Jan 2005 11:07:23 +0000

Nicholas O. Lindan wrote:

>_ALL_ programming languages [allowing for enough memory and
>addressing] are equivalent. Look up 'Turing'.

I believe that you have it backwards. A Universal Turing Machine
is the equivalent of any computer running any programming language,
but not all computers or all programming languages are the equivalent
of a Universal Turing Machine. In fact, no computer ever built is
the equivalent of a Turing Machine - they all lack the infinite
amount of memory that the Universal Turing Mmachine has.

Look up 'Turing'.

Universal Turing Machine, Alternating Turing Machine, Oracle
Turing Machine, Probabilistic Turing Machine, or Deterministic
Turing Machine, or Nondeterministic Turing Machine? Please note
that a Universal Turing Machine is, by definition, capable of
simulating any other Turing Machine by encoding it. This includes
Probabilistic/Nondeterministic Turing Machines.

>And they are all _boring_, being deterministic and all.

Getting back to real-world programming languages, why do you assume
that there exists no hardware that provides true random numbers
derived from atomic decay events to the programming language?
Pict, Prolog, Promela, PGC and GOL are all nondeterministic.
In addition, an unpredictable but deterministic programming language
is just as interesting as a nondeterministic programming language.

Interesting gleanings from searching on the above:

"GOL is a nondeterministic programming language obtained by
extending LISP to encompass a modal predicate calculus"

"...an unboundedly nondeterministic programming language, the
Partial Guarded Command language -- which includes partial
commands, nondeterministic choice, 'random assignment' and
recursion ... No restriction is placed on possible nondeterminism,
which may be bounded, countable or uncountable ... The following
logics are derived: Dijkstra's calculus of predicate transformers,
Hoare logics for partial and total correctness, a novel logic of
invariant relations, and a temporal logic." 

-- 
Guy Macon <http://www.guymacon.com/>

Relevant Pages

  • Re: a language is a language
    ... We might also define a programming language ... Without a reference to the syntax ... and semantics, it cannot be parsed, even by an arbitrary carbon-based ... The point of the Turing Machine equivalence, ...
    (comp.programming)
  • Re: Refutation of the DisProof of the Halting Problem
    ... > It is a very surprising turn of events. ... > a Turing Machine, but something less. ... Turing's may admit a program that decides the model's halting ... Halting is undecidable in any programming language that ...
    (comp.theory)
  • Re: Refutation of the DisProof of the Halting Problem
    ... > It is a very surprising turn of events. ... > a Turing Machine, but something less. ... Turing's may admit a program that decides the model's halting ... Halting is undecidable in any programming language that ...
    (comp.lang.cpp)
  • Re: Refutation of the DisProof of the Halting Problem
    ... > It is a very surprising turn of events. ... > a Turing Machine, but something less. ... Turing's may admit a program that decides the model's halting ... Halting is undecidable in any programming language that ...
    (sci.logic)
  • Re: Refutation of the DisProof of the Halting Problem
    ... >> It is a very surprising turn of events. ... >> a Turing Machine, but something less. ... > Turing's may admit a program that decides the model's halting ... Halting is undecidable in any programming language that ...
    (comp.lang.cpp)