3 ms·
BRB, implementing a x86 interpreter with O(2^n) memory overhead.
by reuben364 3y ago
BRB, implementing a x86 interpreter with O(2^n) memory overhead.
- adamnemecek 3y agoThat's the brute force approach.
- reuben364 3y agoI guess the alternative is just bounding the number of instructions and proving inside or outside your language that it is sufficient for your program.
- adamnemecek 3y agoIndeed, that's what bounded means.
- reuben364 3y agoYes, but the point is that you are giving a constructive existence proof for that bound. You asked for why there are so few total languages. The answer, as far as I'm aware, is either brute force on a fixed amount of memory or giving provable bounds either by decision procedure on a restricted language or having to manually give a proof on a more expressive language. Is that that an answer to your (presumably rhetorical) question?