|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |