3 ms·
Yes, but even if your language is total you have an analogue of the halting problem, where instead of analysis being undecidable it just takes an unrealistic am
by tree_of_item 9y ago
Yes, but even if your language is total you have an analogue of the halting problem, where instead of analysis being undecidable it just takes an unrealistic amount of effort.
- asynchrony 9y agoMy understanding is more hand-wavy than formal, but would the combination of a total language and some limitation on the total number of instructions produce a provably predictable language?
- lmkg 9y agoLikely not. It takes only a very small number of instructions to implement an interpreter for a Turning-complete language, and then you can create arbitrary behavior by passing different input. The number of necessary instructions is shockingly small, if using something like Binary Lambda Calculus or Subtract-And-Branch-If-Negative.