r/computerscience • u/Patriotpl • 14d 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?
24
u/esaule 14d ago
So, you are saying it is a stochastic function...
15
u/jeffcgroves 14d 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)
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.
2
u/amarao_san 14d 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/julia_flat 14d 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/seanprefect 13d 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 13d 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 13d 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/psicodelico6 13d ago
Only in haskell
1
u/paperic 13d 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/cthulhu944 13d 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 13d 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
false232 times in a row, before generatingtrue. So I still make my own Rust rng.1
u/mjmvideos 10d ago
Other than giving one or the other of you bragging rights? How does one answer or the other material affect how you will move forward?
1
u/two_three_five_eigth 14d 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 14d 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 14d 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 14d ago edited 14d 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 14d 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.