0:00:00.000,0:00:06.380 So, how can we now simulate a non-deterministic RAM on a RAM? 0:00:06.380,0:00:12.360 Because that is what we originally set out to do and it turns out, it's actually not that difficult 0:00:12.360,0:00:15.450 once we have our deterministic RAM simulator 0:00:15.450,0:00:18.780 because what happens if you're in a given line or code? 0:00:18.780,0:00:23.700 There's two different things that can happen, one it's a normal instruction such as 0:00:23.700,0:00:27.210 one you would find on a deterministic RAM and in this case, 0:00:27.210,0:00:31.870 the simulator can just go on running the same way that it would have gone for the deterministic RAM. 0:00:31.870,0:00:38.350 The only difference is if the simulator encounters this, if better, here then it has a problem 0:00:38.350,0:00:42.840 because then simulating what this line of code does is not straight forward anymore. 0:00:42.840,0:00:47.730 The if better might execute the first part of the code or the second part of the code 0:00:47.730,0:00:52.990 around which it has written, so we have to work a little bit on this part here of the simulation. 0:00:52.990,0:00:54.660 So, we have to distinguish two cases. 0:00:54.660,0:00:59.950 One is if we have a normal instruction, then we'll just do a simulation, 0:00:59.950,0:01:04.040 but if we have an if better, then we don't know how the machine continues 0:01:04.040,0:01:09.670 so what our simulator would then do, is it will branch into two different possibilities. 0:01:09.670,0:01:12.870 So it will start two new simulations. 0:01:12.870,0:01:19.590 In one simulation, it will continue assuming the if better function executes the first part of the code, 0:01:19.590,0:01:22.550 so the one that came directly after the if better. 0:01:22.550,0:01:26.880 And then the other case, it will continue assuming that the if better function 0:01:26.880,0:01:31.800 executes the second part of the code, so the part that comes after the else statement. 0:01:31.800,0:01:36.320 And of course, once you have this branching, you don't have one single simulation anymore, 0:01:36.320,0:01:38.690 but you have to continue with two simulations. 0:01:38.690,0:01:43.850 One simulation makes this assumption here, the other one makes this assumption down here. 0:01:43.850,0:01:50.010 And if you now encounter the if better statement, then again, 0:01:50.010,0:01:54.420 you will have to branch into two possibilities up here and the same thing down here. 0:01:54.420,0:01:58.290 If you continue the simulation with the assumption what happened the first time 0:01:58.290,0:02:01.670 you encountered the if better function, and now you go on, then again, 0:02:01.670,0:02:07.010 if you find, if better, again you will have to split into two different possibilities. 0:02:07.010,0:02:11.980 And of course, running a simulation this way where you have to split into two possibilities 0:02:11.980,0:02:15.820 all the time comes at a price which I'm sure you can figure out by now. 0:02:15.820,0:02:20.790 And my question to you is, if we have a program that uses the if better function, 0:02:20.790,0:02:26.790 and times, how many simulations or how many different simulations do we end up running? 0:02:26.790,9:59:59.000 Is it n simulations, is it n² simulations, is it 2^n simulations, or something else?