Talk:Broken Calculator
Calculating crash percentage
Here's the formula for the probability of a program crashing (in percent) in Desmos. You should look for the x values in the graph for the ranges.
- l = [number of instructions in program (except note)]
- r = x/4
- R(x) = {x ≥ (floor(x) + 0.5): floor(x) + 1, x < (floor(x) + 0.5): floor(x)}
- f = R(10l / r)
--Europe2048 (talk) 21:09, 28 September 2023 (UTC)
Is it Halting?
The chance of crashing is always greater than 0, which ensures that every program in the language must halt. Therefore, this programming language does not meet the criteria for Turing Completeness because the Halting Problem is decidable for all possible programs.
This language actually brings up an interesting philosophical question. At every step, the language has a nonzero probability of halting. That means even an infinite loop halts with probability one. But it won't always halt, just almost always. There exists a program that will, with probability zero, run forever. And, more usefully, for any finite number of steps N, there is a program that will successfully run for at least N steps, with probability strictly greater than zero. I think a not-unreasonable argument could be made for Turing completeness here.
--Mercerenies (talk) 17:50, 12 February 2024 (UTC)