Given the current state of a system, all future states can (in principle) be extrapolated.
Another way of saying this is that the complete information of all future states is encoded within the present state. That's also to say, information is conserved1. The "in principle" is to cover for the fact that in practice, you may need infinitely precise measurements to determine the current state, and infinite computational power to do the extrapolating. But so long as you have a theory which can mathematically turn one state into the next, then the system is considered deterministic.
We will study the simplest (nontrivial/degenerate) state-space I can think of to toy with this concept: a dynamic bit, under discrete time. I will label the two states ↑ and ↓. The "history" of a system can then be represented by a string of states, such as:
↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑
Ignoring the boundaries, the above system is obviously deterministic. If you know the current state (say ↑), you can easily predict the next state (↓), and the next after that (↑), and so on. The "law" is that the bit simply flips at each moment, so that neighboring moments are always opposite each other.
Here's an "obviously nondeterministic" system:
↑↓↑↓↓↑↑↑↑↓↓↑↑↓↑↑↑↑↑↓↓↑↓↓↓↓↓↑↑↓↑↑↑↓↓↑↑↑↑↓↑↓↓↑↓↓↑↑↑↑↑↓↓↑↑↑↓↓↓↑↓↑↑↓↓
This is a random bit string I've taken from an online generator. In it, sometimes ↑'s are followed by ↓'s, and sometimes they're followed by ↑'s. Thus, if the system is currently in the state ↑, one cannot predict whether the next state will be ↑ or ↓. The next state is not encoded in the current state. Therefore, it's nondeterministic.
It would seem, then, that there are only 3 ways for the dynamic bit to behave deterministically:
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑
This corresponds to the fact that the state-space has 2 automorphisms, and 2 initial conditions, leaving 4 possible histories, 2 of which are equivalent (just shifted by 1 unit), leaving 3 unique options. More simply put, there are only 2 possible "laws of motion" for the bit which only consider the current state: stay the same, or change.
Here is where I will begin to challenge this notion of determinism...
Let's study another history which is... "sort of" deterministic:
↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑↑↓↓↑
It goes up twice, then down twice, then up twice, and so on.
Just as in the random case, one cannot predict the next state purely based on the current state. If all you know is that you're currently at ↑, you cannot predict whether you will next be at ↑ or ↓. However, this system is obviously extremely predictable: it simply flips every other moment. We are in a strange situation where the system is apparently both completely predictable and nondeterministic.
You may notice that the predictability of this system hinges on the observer having a memory of the previous state. The current state isn't enough to make predictions, but the current state and the previous state are2.
Here's what we can do: simply redefine what constitutes the "state" of the system. The state of the system at a given time is now defined by both the current and previous bits. It's the same system, we've just characterized it differently. We can now write the history as a series of {current, previous}, like this:
{↑,↓}, {↑,↑}, {↓,↑}, {↓,↓}, {↑,↓}, {↑,↑} ...
If I'm at {↑,↑} now, I know I'll be at {↓,↑} next3. We've recovered determinism.
That might sound like cheating, but it's actually something physicists already do. The future positions of particles cannot be predicted purely from their current positions. You also have to know their velocities; that is, the rate of change of the positions, which essentially defines the current state as containing a memory of the infinitesimally-previous state.
There's still a sense in which this really feels like cheating, though. After all, if we're allowed to redefine the state-space to include any information we want, can't any system be considered deterministic? Let's take that random system from earlier...
↑↓↑↓↓↑↑↑↑↓↓↑↑↓↑↑↑↑↑↓↓↑↓↓↓↓↓↑↑↓↑↑↑↓↓↑↑↑↑↓↑↓↓↑↓↓↑↑↑↑↑↓↓↑↑↑↓↓↓↑↓↑↑↓↓
...and assign each moment a number:
{↑,1}, {↓,2}, {↑,3}, {↓,4}, {↓,5}, {↑,6}, ...
This is my new state-space. Now, I will create a function, f(x), which takes an integer and returns either ↑ or ↓, according to the list of states above. It acts effectively as a "map" of all future states of the system. Rather than describing the future by equations, it simply lists everything that will happen.
So, despite the fact that this is literally a randomly generated system, I have nonetheless come up with a "law of motion" which can predict all future states, given only the current state. So... is this system deterministic? And if so, is there even such a thing as a nondeterministic system?
You may complain about my "law of motion" simply being a list of all the states, but the only thing mathematically separating it from a physics theory is a lack of pretty compression. It's just as "valid" of a law. Now, you may also complain that this theory is utterly impractical, as it requires the observer to already know the complete history of the system. This is completely true, and an important point, but it does not undermine the fact that it is a legitimately deterministic model of a "random" system.
My takeaway from all this is that determinism is not a property of systems. It is a property of theories. The system will do as it does, it doesn't care whether we can predict its behavior. Predictability in-principle is a feature of a predictor, not the object of prediction. Anything is "deterministic" if you know what will happen in advance. Classical Mechanics is deterministic because it predicts the next state given only the current state. The Born Rule in Quantum Mechanics is nondeterministic, as it only predicts probabilities. If we discovered tomorrow a new theory which can predict exact states, we shouldn't say that the universe was deterministic all along. Rather, we will simply have moved from a nondeterministic theory to a deterministic one.
Of course, if we remove the "in principle" from our definition, things change. Who cares if a completely random system is predictable given a map of all future states, we don't HAVE a map of all future states, that's the whole point! In practice, some systems are definitely more or less predictable than others. This distinction about determinism may only be relevant to thought experiments and time-travel stories. Regardless, I thought it was worthy of some consideration.
2 I haven't discussed reversibility so far, but all of these deterministic systems are also reversible. Reversibility is the same as determinism, but backwards rather than forwards in time. In this case, a memory of the previous state will allow you to predict all past states as well. The same goes for a "memory" of the next state. Really, knowledge of any two odd-number-separated states will grant full knowledge of the entire history. For example: "↓--↑-" can be filled in as "↓↓↑↑↓", but "-↓-↑-" is ambiguous, as it could be either "↑↓↓↑↑" or "↓↓↑↑↓".
3 This "law of motion" can be described in plain English as: If the two arrows match, the first arrow flips. Otherwise, the second arrow flips. Or in more formal-sounding terms: For state {a,b}, if a = b, the next state is {not a, b}; else, {a, not b}.