2
$\begingroup$

I'm not exactly sure whether this question belongs to this SE or not, but it doesn't seem to fit elsewhere.

Say a process behaves in a deterministic fashion (that is, it gives the same output when an input is entered over and over again), then can we build it as an algorithm?; if not, can you think of a counter-example?, that is, a deterministic process which can't be modeled as an algorithm.

$\endgroup$
5
$\begingroup$

An algorithm must have a finite description, whereas a deterministic process according to your definition can use an infinite lookup table. For example there is a deterministic process that solves the halting problem for Turing machines, but there is no such algorithm.

$\endgroup$
  • $\begingroup$ I'm wondering then: in which cases do both concepts coincide?; say a deterministic process has only a finite lookup table, can we an algorithm that describes it? $\endgroup$ – Miguelgondu Dec 23 '16 at 22:21
2
$\begingroup$

No. Deterministic, to me, means that the state of a system at any given point in time is a function of its state at any previous point in time. So all one needs to show a difference is an example of a system that evolves according to a function that isn't computable. For instance encode programs as Godel numbers. The state of a system at any given point in time (where time is discrete) is 0 if the represented program halts and 1 if it loops. This is an example of a discreet deterministic system (all be it an abstract non-physical one). It's also easy to find examples of non-discreet deterministic systems that can't be computed.

I'm not sure if there is some example that can be pulled from physics or not. Quantum systems themselves can be simulated but there might be properties of them that can't be computed there from. I know of something called the "spectral gap problem" but I'm not sure how that plays into your answer and moreover you might not call a quantum system "deterministic" because of how measurements work in quantum systems.

Another possible, but more philosophical, definition of deterministic would be the lack of presence of free will which you might think a quantum system qualifies as. But I don't think that's what you were looking for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.