# Probabilistic / Nondeterministic Turing Machines

#### Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

•  Subject
• Author
• Posted on

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.

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/

Re: Probabilistic / Nondeterministic Turing Machines

"Guy Macon" <http://www.guymacon.com/ wrote in message

He did say "allowing for enough memory and addressing," and I think he meant
to leave out programming languages that were bizarrely restricted (e.g., a
language with no conditionals or something like that) - he's talking about
real programming languages.

In Prolog, "nondeterminism" means the ability to backtrack among
alternatives.  It has nothing to do with determinism in the philosophical
sense, i.e., the predictability that might be missing from atomic decay,
depending on what you believe about quantum physics.   Nondeterministic
Prolog programs are perfectly deterministic in the metaphysical sense.

I suspect the same is meant by "nondeterminism" in the other languages you
mention, though I'm not familiar with them.

Re: Probabilistic / Nondeterministic Turing Machines

Thanks! This is rarified stuff for an assembly language hacker
such as myself, and I apreciate the correction.

I do believe that, for example. Linux and any programming language
that runs on Linux and has a random function is not deterministic
in the metaphysical sense.  To argue that it is deterministic is to
argue that yu have the CPU, memory, etc. but do not have the various
sources of physical entropy that feed /dev/random (in my case it is
fed by a quantum-based hardware random number generator that works by
measuring the mtime between radioactive decay events.) I also don't
believe that a simple program running on a 4-bit uC is deterministic
in the metaphysical sense if I keep a fast memory increment loop
running and sample it when a key is pressed.

Re: Probabilistic / Nondeterministic Turing Machines

I'm curious - how do you test that it's a) present b) working c) "truly
random"?

Steve
http://www.fivetrees.com

Re: Probabilistic / Nondeterministic Turing Machines

I look at the box and note that nobody has stolen it yet.

b) working

If it breaks, the Von Neumann compensator in the driver stops putting
out bits and any application that uses a blocking random number input
hangs or times out.  In addition, I occasionally look at the raw output
with my oscillosope - usually right before doing something critical.

c) "truly random"?

One can never be sure, but I test it every so often with The Diehard
battery randomness tests, again usually right before doing something
critical.  The chances of a hardware failure that makes the output
non-random in such a way as to pass the Diehard test is quite small.

"The generation of random numbers is too important to be left to chance."
-Robert R. Coveyou, Oak Ridge National Laboratory

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