In general, whether programs will stop, or not, is impossible to predict {halting problem}|, as shown by Turing.
Turing machine
Turing machines must have at least one rule that leads to STOP, must not move to non-existent state, must use and make only coded sequences of marked and blank squares, and must have at least one marked square on output side. Turing machines have input and rules. Number of Turing machines and number of inputs are both infinite.
Many Turing machines never reach STOP.
If people can prove that Turing machine with some input reaches or does not reach STOP, people can make complex Turing machines that include that Turing machine and answer the question whether Turing machine stops. People can program complex Turing machines to make same mark, as long as that Turing machine does not stop. Complex Turing machine can include all Turing machines, so then all Turing machines can mark definite answers for inputs, whether they stop or not. Therefore, one algorithm decides same Turing machine reaches STOP, and one algorithm decides same Turing machine does not reach STOP. However, only one algorithm is true, and the other is false. Therefore, it is impossible to prove that Turing machines will reach STOP.
halting problem
Possible Turing machines have representations as natural numbers. Possible inputs have representations as natural numbers. If numbers of inputs and machines are equal, a square natural-number array can represent all possible Turing machines and inputs. See Figure 1.
Look at sequence, to take diagonal slash, on square-array main diagonal. See Figure 2.
Change marks for numbers in diagonal sequence. See Figure 3.
This sequence is not the same as any row or column sequence, because it differs from first row and column at first number, differs from second row and column at second number, and so on. If halting problem is solvable, this sequence can represent possible Turing machine/input combination, because first part can be legitimate Turing machine and second part can be legitimate input. However, array must contain all possible sequences, because array has all possible Turing machines and all possible inputs. Contradiction makes halting problem not solvable in general.
omega
Programs have halting probabilities {omega, number} {Chaitin number}. Data bits can be input to program until program does not request another bit, because it has stopped. Random-bit input stop program after different numbers of input bits. Probability that program stops is 0.5 raised to number of bits. To find total halting probability, add random-input-experiment probabilities. Using more random-input experiments can approach omega.
Mathematical Sciences>Computer Science>Systems>Complexity Theory
3-Computer Science-Systems-Complexity Theory
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0224