Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Warp wrote:
>>>   I don't think so. The very definition of "deterministic" is predictability.
> 
>> That's where we disagree. It's completely possible to be both deterministic 
>> and unpredictable. Indeed, that's exactly what the halting problem is all about.
> 
>   But a deterministic program will always behave the same way. It doesn't
> change its behavior from one execution to another. Thus it behaves predictably.
> "It will do the same thing it did the last time."

Only if presented with the exact same input.  And you have to run it at 
least once to find out what that result is.  And, in the real world, once 
you've run it, its previous choice has become part of the input for the next 
run. You cannot present a human with the same choice twice.

A turing machine you couldn't start in a known state would be both 
deterministic and unpredictable.

Now, I guess you could investigate free will if you could travel in time and 
see whether the same events lead to the same results, but that would require 
there being no randomness either.

>>> The very word itself is saying so. It's the opposite of "non-deterministic",
>>> which is unpredictability.
> 
>> Also not quite true. Non-deterministic turing machines are very predictable 
>> in their behavior.
> 
>   If it's non-deterministic, you cannot say how it will behave the next time
> it will be executed.

You can if it has exactly the same input.  (Assuming there's only one 
shortest path to the halting state, of course.)

I'm just pointing out that "non-deterministic" doesn't technically mean it 
behaves differently each time. It simply means it's unpredictable *before* 
you run the program. With the same input, an NDTM will run the same steps 
each time. You just can't tell what those steps are before you run it.

>>>   A chain of events is deterministic if it happens in a certain way because
>>> there's no other way it could have happened. If the exact same initial setup
>>> can be replicated, then the chain of events will happen in the exact same
>>> way again, completely predictably. That's the very definition of
>>> deterministic.
> 
>> Yet, oddly, NDTMs behave that way. ;-)
> 
>   If it always behaves the same way, isn't it by definition deterministic?

Nope.

An NDTM has instructions that could do either X or Y when they're in the 
same state with the same input. That's the "nondeterministic" part. But the 
machine is required to execute the X (or the Y, whichever) that will cause 
it to halt in the fewest number of steps. Which will it follow? You can't 
tell, because you can't solve the halting problem.  If it *does* halt, and 
you feed it the same input again, will it follow the same steps again? Yes. 
(Unless there are two paths that each lead to halting in the same number of 
steps, at which point you really don't *care*, by the definition of the 
math.)  I.e., an NDTM will factor the number 18372819 the same way every 
time: it'll guess that number's factors, and print them to the tape. You 
just can't tell by looking at the machine what it'll guess.

I don't think you can tell if something's deterministic or not if you can't 
examine its inner workings and you can't feed it the same input twice. Both 
of these are true for people.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message