r/computerscience • u/Patriotpl • 1d ago
Discussion Is simulation a function?
Question to settle a debate which I recently had with two of my colleagues.
One of my colleages argued all simulations are mathematically functions by definitions, since for every set of arguments they need to return one outcome. As an example we took a cellular automaton simulating a forest fire. They stated that everytime you give it a particular starting state, the end state will be the same, but I don't agree with that. To simulate humidity or different wind speeds and directions one might use an rng, so the same start map run twice might give 2 different results, which means it's mathematically not a function. My friend countered that because of how rngs work, with the same seed the will always be the same. You don't need to set a seed tho and I can imagine cases when it's even by design - for example when you can't be sure which direction the wind will be coming from and you want your simulation to account for any of them.
But here's the bit that we couldn't agree upon. My friend said, that even without seed, or using quantum randomness, that randomness is always based on something and as such must be treated as kind of a baked in argument. Because of that, if you manage to somehow recreate the exact same "randomness state", the outcome will never change.
From my point of view that's not the case. Even using simple time based pseudorandom number generators, to you as someone analysing such simulation, that rng should not be treated as argument. The way I see it it's just a black box, that "magically" gives you a number, you should treat it as truly random and use it to approximate all the different variables, that are too complicated to calculate each and every time you run the simulation or are just out of scope. Therefore the same input can give you different outputs, which makes the simulation itself not a function by mathematical definition.
What are your opinions on this?
13
u/jeffcgroves 1d ago
Mathematically, someone has proven all computer programs are functions, even those that use psuedo-random-number-generators (pRNG), provided the seed is based on something deterministic. I know you said "rng should not be treated as argument", but that's cheating. The RNG clearly is an argument (or computed from a deterministic value)
using quantum randomness
This is the only real question. Is a qRNG a function? You could argue that the value of a qRNG from a specific source at a specific time is a function (two inputs, one output), but one that can't be determined in advance. So, it IS a function, but you can't write down the function ahead of time.
1
u/Patriotpl 1d ago
That sounds correct. What about simulations that aren't computer programs?
1
u/jeffcgroves 1d ago
I think you can pedantically apply the same argument to reality, since no two events in spacetime are completely identical. Issues:
The Heisenberg Uncertainty Principle states you can't measure the current state of the universe, which would be your input. Quantum mechanics says that it's meaningless to ask if something exists if it can't be measured. If you accept both these statements, your function wouldn't have an input.... unless you enumerate all possible quantum realities based on the measurable part of your current universe and use that as input [actually, there's a better way, see below]
Note that you don't have to accept both these concepts. Determinists would argue the universe has state even if portions are unobserved and that quantum mechanics isn't truly random but uses hidden variables
If you accept multiple universes theory, there could be many "outputs" to a given collection of input quantum states, but that's fine.
So your "input" would look like a list of all observable variables, including local time, with error margins based on the Uncertainty Principle. Per quantum theory, you can exclude any variables that are not observed since they don't actually exist.
Relativity theorists would point out time varies with location, and that your observation of the universe is therefore limited. We don't and can't know what's happening on Alpha Centauri now, only what happened ~4.5 years ago
We can now put most of the load on the function. The function must calculate all possible universes based on our inputs. This includes, for example, all possibilities for what Alpha Centauri has done in the last 4.5 years. Since our input measurements are necessarily inaccurate, it would have to compute all possible "true" values and the likelihood of those values occurring
The output would then be a probability space of possible universes that are consistent with your observations.
The problem, of course, is you want to know: if I tweak this, what will happen? However, if you accept quantum randomness, there literally no answer to that question. You have to input everything you know to get a probability space of possible outputs.
This is why I believe the Earth is flat :)
1
u/not-just-yeti 11h ago
the value of a qRNG from a specific source at a specific time is a function (two inputs, one output), but one that can't be determined in advance.
Or, that the result is a probability-function.
2
u/amarao_san 1d ago
Pure mathematical function can't have 'rng' in it, because there is no special meaning for t (time) in math. There is no 'every time' there is no 'after'. You define one from another in non-temporal way. a=2 means a is 2 for the scope of 'a', and not for some duration.
So, to simulate externalities like that, in computers, there is a thing called effects and coeffects. Effects are things function cause outside when called, and coeffects are things which influence function outcome (e.g. time.time() in Python, which returns current time has coeffect of wallclock time).
So, for a given coeffect function produces the same outcome. True rng input is coeffect (and often is IO operation from a specialized device), which can be emulated.
Pure simulation is a function.
Things become hairy if you have external logic influencing coeffects based on previous effects.
Imagine a function which pinches a human (effect in a form of signal to actuator) and waits for a reaction, process this reaction and uses it for future reasoning. It won't get the same coeffect on each effect. First one will be success, second maybe, third is possible only if human is immobilized.
So, with coeffects only, simulation is a function. If it does something and wait for result (e.g. start a fire and checks if there is a smoke) no, it's not a function anymore.
-1
u/Humble-Captain3418 1d ago
You have written a very long comment to say that Information Theory does not exist. We can model before, after, instants in time as well as recurrent behaviours.
0
u/amarao_san 1d ago
Yes and no.
You can model processes which are meaningfully encoded in the known algorithm.
If significant part of the resulting system behavior is dictated by external reaction (coeffects) due to specific effects, you can't.
Imagine a system, where you get your goal as chain of interactions with external hard-to-predict system. Like chat with LLM, and it needs to be in dialogue with user to understand what user wants.
You can simulate it in terms of the fixed input, but they are not true anymore, because this chain:
Fixed input1
Fixed output1
Reaction of input2 on output1
Output2 based on input2
Is defined by #3, and today it's different than yesterday, and it is correct now. It was correct yesterday, but was different. (because yesterday was day before deadline, and now it's a day after deadline).
So, when a meaningful part of the system is defined by effect-coeffect, the code is no longer mathematical function, it lost reproducibility.
1
u/Humble-Captain3418 1d ago
You've just defined that there is an input2' that is independent from output1, s.t. input2 is a function over input2' and output1. We can therefore compose output2 as a function of input1 and input2'.
If you also wish to model the time-sequencing of the two outputs, then I'd like to introduce you to the Dirac delta function.
1
u/amarao_san 1d ago
input2 is dependent on outpu1. I said that. But it's also dependent on external state, which is non-reproducible.
Therefore, all interaction is either pre-recorded (and no longer true), or can't be reproduced.
Imagine that intput2 is dependent on timing of the output1. It happens all the time with LLM.
Function does not control execution time (which is effect of computation and of external state), but execution time is control input2, and output1-input2 is part of the system.
1
u/julia_flat 1d ago
I would recommend you look into the IO monad, where you essentially pass the outside world into a function as an argument. This lets functions that use physically based RNG still be pure (“mathematical”) functions.
1
u/BarcodeEmperor 15h ago
Friend mentioned here. Passing entire universe as a variable of a function was exactly what I was thinking, though this discussion involved some alcohol at 3am and I might have not been strict formally at that time
1
u/seanprefect 1d ago
I’m going to use the term subroutine to define something that is a consistent set of instructions but is not necessarily a function. (It’s not perfect but whatever and yes i known the word algorithm exists ) Let’s simplify this to its core question. Let’s say you have a subroutine that says “take the number of inches of rain that have fallen in a 24 hour period specified by me, over this specific area specified by me , multiply it by 10 and return the value) I’d argue that’s a function , you don’t necessarily know the value before hand but you can repeat it with the exact same parameters and expect the exact same answer. Even if the values themselves aren’t necessarily known.
Let’s take it a step further, “ take the number of inches of rain that have fallen in the past 24 hours over an area specified by me and multiply it by 10” We lose a degree a determinism, and can no longer use the exact same inputs to get the exact same outputs since one of them is a fixed moment in time. Is this a function ? I’d argue no because f(x) remains deterministic but it’s no longer reliably repeatable or predictable.
1
u/iLrkRddrt 1d ago
What about weather forecasts? They're literally just prediction simulations, and as we all know they are not infallible.
Your friend is forgetting a very subtle, but easily observable phenomenon in his assumption: Chaos Theory. This is why you want to run a simulation many times, so the mathematical law of large numbers can balance out unpredictability of chaos; even then though, a simulation is never a discrete problem.
1
u/dnabre 1d ago
Ok, bunch of idea floating around here. I'm going to take "simulations" as being basically any kind of program here, with the possible limitation that it's not interactive - a program reading input from somewhere, runs, and outputs to somewhere.
The property your colleague is describing is called referential transparency. Very briefly, if you call a function with the same input, you always get the same output. This is an extremely useful property for optimization and reasoning about programs (two very intermingled things in practice).
In CS, we have the term 'pure function'. It's a function that has referential transparency and has no side effects. By side effect, we are talking about changing anything anywhere. Modifying the value of a variable (one inside the function that are reset the next time you run it don't count), making other code run that would have side effects, or any kind of I/O. These 'pure functions' are basically the same a mathematical function. Side note for thought, can a pure function crash?
They have a lot of useful properties. Since they will always give the same output for a given input, you don't need to run the function for the same input twice. They can be easily isolated for testing, since the function is effectively self contained, and the order in which you execute pure functions relative to each other doesn't matter. This makes them great for doing any kind of parallel programming. Without side effects, you can have thousands of threads running the same function, and nothing is going to interfere with each other. Avoiding side effects has become a good practice to avoid programs with multithreading of all sorts. Functional programming languages often to stick to this idea as much as possible. Side effects though are pretty useful for programming though, you generally want to read input from somewhere and output to somewhere. There are some really fancy ways to making the two things mess (e.g. monads).
Back to mathematical functions, what if we had a function that took in the entire state of your computer, and returned a new state. In theory, that is what a computer is actually doing. If it wasn't for concurrency, synchronization, and all the magic that modern microprocessors due do, you could think of evaluating that function as begin analogous to executing a single machine instruction. You computer is just transforming from one state to a next, with each new state just being this function applied to the last. In the theory of computation, that is what we actually do. We think of machines (those being mathematical objects) as transformations (i.e. functions) from one state to the next.
With pseudo-random number generators (pRNGs) don't change any of this. They are just mathematical functions that map the last number they generated plus some amount of extra state, into the next number "random" number with new state. The seed being the initial number and state that it starts from. In practice, many pRNGs get seeded with something relatively predictable, like the exact time your program start running (down to the microsecond). But the computer's clock can be easily wrapped up into the iterative function application to states. The current time just being incremented at each evaluation by a value equal to the time it takes to do it. All of this so far is the deterministic world.
Warning, I'm not physicist or an expert on computer randomness, so take this be as broad overviews at best. For most important stuff (crypto, security, etc.) we want a more truly random value than just a function that jumps all over the place (i.e. pRNG). Exactly what true randomness is a pretty hard thing. Prior to quantum mechanics, many people didn't think it existed (Einstein is famously credited with saying "God does not play dice with the universe"). Computers nowadays get their "real" randomness from a bunch of places, that is entropy, from each and mix them together. There a lot of different sources for entropy inside your computer, an easily understood one is thermal randomness of a CPU. Billions of transistors filling all over the place, in something extremely tiny, make the temperature fluctuate in extremely hard to predict ways. Measure that temp very precisely, and only pull the smallest few digits from it. Is that better or worse than having a webcam pointed at a wall of lava lamps, and using the changes to that image as your entropy source?
Randomness discussions can quickly end up bumping into free will in uncomfortable ways.
So where does all of that leave us? If we ignore true randomness (whatever that may be ), computers are just mathematical functions iterating through states, with the state space being incomprehensively huge. If you include that true randomness, that doesn't seem to work, but very little else (if anything) in reality works either. You have also taken a huge step outside of the realm of CS, and arguably math as well.
1
u/BudgetEye7539 11h ago
It is also possible to formulate PRNG as a periodic function of some integer argument (index of the sequence member) and some integer parameter. Moreover, the most robust PRNGs are made this way, I mean AES-CTR and ChaCha.
1
u/Yoshibros534 8h ago
I’m vaguely aware you can simulate crashing in a pure function using something called a “maybe monad”, but i no idea what exactly that means
1
1
u/paperic 15h ago
A function "argument" is absolutely anything upon which an output of a function depends on.
So the RNG is an argument, albeit a silent one.
The entire concept of pure functions is that it has no side effects, doesn't depend on any external state and it doesn't have any internal state.
The PRNG has a state.
If the prng seed is generated from the current time, and clocks need an internal state.
If the PRNG seed is generated from some mouse movements then the mouse movements are an argument.
If the seed is generated from some quantum state, well, that's an external state.
1
u/BudgetEye7539 11h ago
And what is about PRNG that don't have a state and that can be explicitly formulated as a pure function, just as sine or cosine? You give them the index of the sequence member, some parameter and they will return a pseudorandom number. Moreover, the most widespread PRNGs are made this way.
1
u/paperic 8h ago
Then that index you're passing into the PRNG has to depend on some parameter to your function.
Or, alternatively, the function has to use a constant index, which makes the random number a constant.
Otherwise your function is not a pure function in the mathematical sense.
1
u/BudgetEye7539 7h ago
It also can just use a second argument, the seed or the key. Counter-based PRNG work this way.
1
u/paperic 7h ago
Yes, but where do you get that argument from?
If you let the caller pick any argument as the PRNG seed, then the simulation can be a function.
But and if you're using a PRNG that's been already seeded, you can consider the seed of the function to be a silent argument to your function.
I'm not actually sure what you're trying to say.
1
u/BudgetEye7539 7h ago
This argument can be passed to the simulation as the "sequence ID" or seed. And the simulation can call the stateless PRNG using this seed as the second argument.
1
u/cthulhu944 12h ago
I think there is a lot of hair splitting going on here. The RNG call in the simulation is just an additional input/parameter to the function. You could rewrite the simulation to include either the seed or the random number as an explicit parameter.
1
u/not-just-yeti 11h ago
Lots of good answers in this thread. As a (mostly-functional) programmer here, I'll chime in with a meandering answer:
I try to write code as a pure function, when convenient. (It sounds like your colleague is coming from that same mindset.)
When writing code that uses an pRNG, I'll write its seed as an input or at least think of it that way. If nothing else, it's a big win for unit-testing.
A common caveat on writing things functionally: If some small helper-function uses an rng, it'd be a massive pain to have the rng be a top-level input which gets passed along to a thousand other functions just because they eventually call the helper which uses the rng.
A strategy here could be: use a top-level global variable; or, have a top-level global hash of "environment variables", or I'd actually use the OS's concept of environment variables. (But those'd be well-documented, and I'm still thinking of them as inputs.) Also, if my language supports optional keyword arguments, then a function's signature makes it clear that there is a dependency on the "global" state, but if the caller doesn't bother passing it in it'll use whatever mock-or-real-objects I defined when starting the program.
Similarly for things like
timeOfDay()or database connections, I'd have mock generators/versions of these for testing, and think of them as inputs.
When I go to production, then the mock rng/time/database is swapped in with a real one.
I was heartened to recently learn that Rust provides a mock-rng StepRng as part of its standard library! Usually I'm rolling my own for each language (and I'm sure many others are, too). The downside of Rust's particular rng setup is that is StepRng class is that for booleans, it generates false 232 times in a row, before generating true. So I still make my own Rust rng.
1
u/two_three_five_eigth 1d ago
No. Google side-effects. A large part of simulating a real system is making sure the side effects are the same.
0
u/saw79 1d ago
I think you can pretty trivially define it such that it is a pure mathematical function. For example, if world state s = f(t) where t is a global time parameter. If you have randomness or other effects even beyond that you can keep conditioning on things to keep f pure. For example, s = f(t, r) where r is RNG generator state.
0
u/Headsanta 1d ago
Think about a simulation you might do of a Monopoly game. Where each player has well-defined "strategies" / "rules" that they follow to play the game.
If you wanted to see which player had the better strategy, you might "simulate" the game by using some random number generation for the rolls of the dice.
If you fixed a list of dice rolls, since the stratrgies are the same, the game result would be the same. So this simulation can be thought of as a function f(dice_rolls, strategies) = outcome. And the outcome will always be the same.
However, if you thought of strategies as the only input, then now the outcome is a random variable, and by running it over and over with randomly picked dice rolls, you would now want to estimate p(outcome = win | strategies)
tl;dr, my opinion is that it can be convenient to think of it either way. To make it a function, you'd want to treat the randomness as part of the input to the simulation, but that is an arbitrary choice of how to think of the simulation.
0
u/frnzprf 1d ago edited 1d ago
You can turn any "function" (i.e. program) that uses randomness into a pure function with an extra parameter for the source of randomness. That's an interesting and sometimes useful fact, for example when you want to run code on a graphics card that doesn't have a random number generator.
You can never simulate a system that behaves randomly using pure mathematical functions.
What you should call a "simulation" is just a matter of language.
I would say a system A "simulates" a system B, if they behave the same in a manner you care about.
That means if you wanted to simulate every minute aspect A, you'd need a perfect copy, but if you just want to examine the air-flow characteristics of a car, you can test that with a physical or digital model.
"Isomorphic" is a similar word to "simulates" — something is the same in a certain relation.
0
u/mgruner 1d ago
This is basically what a stochastic process is: basically functions over time that depend somehow on random variables. This is somewhat what your referring to.
Your friend is focused on the implementation portion of it. In that sense, they are correct. Give two "random" systems the same initial state (the seed) and you'll get the same exact evolution over time. Note that this is just a consequence of the fact that we cannot implement truly random numbers easily in real life.
So, from the implementation perspective, your friend is right. The seed is there, and is something actually desirable. From a mathematical perspective you are closer. These systems are not modeled as plain functions, but as stochastic processes. They do not receive a seed as an argument, but do depend on a probability distribution, which is different.
1
u/BarcodeEmperor 15h ago
I was the friend mentioned. In reality the argument went further. If theoretically we took a snapshot of reality at the time we decided to run the simulation and somehow moved back in time to exact same universe state simulation program should return exactly the same output. My argument was that in that case formally it shouldn't even matter if its pRNG or pure randomness, from pure runtime perspective there will always be theoretical seed for an input of stochastic function, even if we may not be able to read it
24
u/esaule 1d ago
So, you are saying it is a stochastic function...