Short answer: Even with perfect knowledge in a purely deterministic universe, not all futures are computable. E.g. see Undecidable_problem
The idea of this paradox is not new, online articles discuss this referencing a paper from 1968 by Michael Scriven and is called "Scrivens paradox".
The intuition that in a deterministic universe perfect knowledge means predictability can be found as Laplace's demon
Long answer:
We can build perfectly deterministic worlds in computer simulations, and we can embed planning agents in such worlds. As an example, you can imagine a Pac-Man machine (https://en.wikipedia.org/wiki/Pac-Man) that runs on auto-play in the background of a bar with some computer-controlled pacman moving in the maze while people have beers and play Darts.
We can see that this is perfectly deterministic, because switching this machine off and on again, the pacman will exactly behave the same. Every. Single. Time. Like a train on rails. No random, no free will.
While this pacman is not a philosopher and has no particular interest in the future or disproving determinism, we can also program it to act in certain ways with a prediction of the future, such as doing the opposite of what we tell it will be happening.
Let's say at the very start of the simulation, when switching on, the pacman is always in a left-right corridor, and can algorithmically only choose to go left or to go right. We can then program it like this:
- if there is no prediction of the future, go left
- if there is a prediction of you going left, go right instead
- if there is a prediction of you going right, go left instead
Now we have perfect knowledge of this deterministic universe. Can we now give this pacman a prediction of its future that is true once we relaunch the machine?
Obviously not. It will always do the opposite.
Does that mean we cannot predict the future in this simulation?
No, we can perfectly predict what will happen in each case, depending on what prediction we give to pacman.
Is pacman thus non-deterministic, a creature with free will and a soul that will go to heaven after death?
No, it's still just a very simple algorithm, acting very predictably according to a very simple rule, still defying our ability to give it a true prediction of where it will go.
We can further implement this using multiple pacman machines. When we switch on the first machine, the pacman will not move, but instead switch on the next machine to see what the pacman there, pacman2 will do, and then do the opposite. So the first machine can use the second machine to get a perfect prediction of it's own future. So pacman2 without any prediction of the future moves left. Seeing that, pacman1 decides to defy his fate and moves right instead.
But what if pacman2 also had a machine, and it chooses first to check what pacman3 is doing before moving? And the same for pacman3, checking pacman4, checking pacman5, checking pacman6... into infinity? This chain of machines would never come to any conclusion of which direction pacman1 will move.
This is a problem of recursion when trying to predict the future of a perfectly deterministic universe with planning agents.
It is an illusion to believe that given perfect information of a system, all future states of that system can be computed. In a perfectly deterministic system, if agents exist that are capable of predicting the future and act accordingly, it is impossible for a machine to exist in the system that can compute the future of the system in all special cases (the agents being able to use such a machine is such a special case).
However like in the pacman example, machines can still be build that predict the future accurately in a lot of cases, even the behavior of agents, but not in the case of the agents being able to use that machine, looking into their own future. In such cases, such machines would not produce any output, but crash or run forever or produce a non-true result.
If that seems unintuitive, that's ok, but consider undecidable problems (https://en.wikipedia.org/wiki/Undecidable_problem) in computer science.
For the problem of our own universe being deterministic and whether we have free will, this does not change anything in the debate.