4 ms·

It's a decidable problem because the duration is bounded (by the best current time).

• shakna 5y ago
  The solution may be easily bounded, but the solver may not be. For example, a simple shift cipher has one solution that simply and easily produces the expected output. However, a one-time-pad is still incredibly difficult to break to demonstrate that output, even when you may know some key parts of the expected output.
  • hakuseki 5y ago
    I'm not sure which part you're saying is unbounded, but everything looks bounded to me. A game is played in finite time, on hardware with bounded operations per second, and AFAIK the NES is a deterministic computer, so the solution does not need to involve any algorithms -- it is simply a fixed sequence of button presses.
    • shakna 5y ago
      > A game is played in finite time, on hardware with bounded operations per second, and AFAIK the NES is a deterministic computer, so the solution does not need to involve any algorithms -- it is simply a fixed sequence of button presses. Glitches allow you to write arbitrary data into arbitrary memory positions. So whilst it is bounded, it is bounded to "any program that can run in less than X time", which as far as I know, is beyond what we can predict within bounded time. The solver may never complete.
      • toast0 5y ago
        Most of the time once you get execution, you jump to the end credits, without a lot of other setup. At worst, you have two phases. Phase 1 is before abritrary code execution, where your inputs are limited by the original program, which usually samples the controllers once per frame; phase 2 would start once you get code execution and could count cycles if need be. Both of these are bounded by existing solutions. We know how many frames, and how many cycles, so you can stop when you get there. Still a very large search space, though.