English subtitles

← 06-12 Simulating A Non-Deterministic Ram

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. So, how can we now simulate a non-deterministic RAM on a RAM?
  2. Because that is what we originally set out to do and it turns out, it's actually not that difficult
  3. once we have our deterministic RAM simulator
  4. because what happens if you're in a given line or code?
  5. There's two different things that can happen, one it's a normal instruction such as
  6. one you would find on a deterministic RAM and in this case,
  7. the simulator can just go on running the same way that it would have gone for the deterministic RAM.
  8. The only difference is if the simulator encounters this, if better, here then it has a problem
  9. because then simulating what this line of code does is not straight forward anymore.
  10. The if better might execute the first part of the code or the second part of the code
  11. around which it has written, so we have to work a little bit on this part here of the simulation.
  12. So, we have to distinguish two cases.
  13. One is if we have a normal instruction, then we'll just do a simulation,
  14. but if we have an if better, then we don't know how the machine continues
  15. so what our simulator would then do, is it will branch into two different possibilities.
  16. So it will start two new simulations.
  17. In one simulation, it will continue assuming the if better function executes the first part of the code,
  18. so the one that came directly after the if better.
  19. And then the other case, it will continue assuming that the if better function
  20. executes the second part of the code, so the part that comes after the else statement.
  21. And of course, once you have this branching, you don't have one single simulation anymore,
  22. but you have to continue with two simulations.
  23. One simulation makes this assumption here, the other one makes this assumption down here.
  24. And if you now encounter the if better statement, then again,
  25. you will have to branch into two possibilities up here and the same thing down here.
  26. If you continue the simulation with the assumption what happened the first time
  27. you encountered the if better function, and now you go on, then again,
  28. if you find, if better, again you will have to split into two different possibilities.
  29. And of course, running a simulation this way where you have to split into two possibilities
  30. all the time comes at a price which I'm sure you can figure out by now.
  31. And my question to you is, if we have a program that uses the if better function,
  32. and times, how many simulations or how many different simulations do we end up running?
  33. Is it n simulations, is it n² simulations, is it 2^n simulations, or something else?