Probabilistic / Nondeterministic Turing Machines

_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
Reply to
Guy Macon
Loading thread data ...

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.

Reply to
mc

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.

Reply to
Guy Macon

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

Steve

formatting link

Reply to
Steve at fivetrees

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
Reply to
Guy Macon

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.