Return to Answer

For many programs P, we can write a decider which halts on any input X, and tells us correctly whether P(X) halts or not. That is especially true for all programs with finite state. It is true for programs without loops, or with loops that have a structure that the decider is capable of analysing well enough.

An example: Let S be a state with a complete and discrete ordering and a smallest value. If S is initialised before the loop starts, and becomes smaller at each iteration of the loop, then the loop finishes and cannot stop P from halting. This allows to prove for example that the calculation of the big Ackermann function halts (in theory obviously. In practice the universe will be long gone before calculating A(4) would finish).

There are programs P where writing the correct decider takes some very hard maths, possibly beyond what we have now. On the borderline: I can easily write a program P where P(n) halts if n ≥ 0 and there are 0 < a < b < c such that $a^n + b^n = c^n$. Only quite recently there has been enough progress in maths to write a correct and very simple decider. (P will halt if and only if n = 1 or n = 2).

Note that a correct decider would have been possible without proving Fermat's last theorem. For example if someone had proved "there are no solutions with n ≥ 3 where a, b, c are co-prime and c > n^10000", that wouldn't prove Fermats Last Theorem, but would allow us to write a decider for the program P.

For many programs P, we can write a decider which halts on any input X, and tells us correctly whether P(X) halts or not. That is especially true for all programs with finite state. It is true for programs without loops, or with loops that have a structure that the decider is capable of analysing well enough.

An example: Let S be a state with a complete and discrete ordering and a smallest value. If S is initialised before the loop starts, and becomes smaller at each iteration of the loop, and the loop stops when the state is small enough, then the loop finishes and cannot stop P from halting. This allows to prove for example that the calculation of the big Ackermann function halts (in theory obviously. In practice the universe will be long gone before calculating A(4) would finish).

There are programs P where writing the correct decider takes some very hard maths, possibly beyond what we have now. On the borderline: I can easily write a program P where P(n) halts if n ≥ 0 and there are 0 < a < b < c such that $a^n + b^n = c^n$. Only quite recently there has been enough progress in maths to write a correct and very simple decider. (P will halt if and only if n = 1 or n = 2).

Note that a correct decider would have been possible without proving Fermat's last theorem. For example if someone had proved "there are no solutions with n ≥ 3 where a, b, c are co-prime and c > n^10000", that wouldn't prove Fermats Last Theorem, but would allow us to write a decider for the program P.

For many programs P, we can write a decider which halts on any input X, and tells us correctly whether P(X) halts or not. That is especially true for all programs with finite state. It is true for programs without loops, or with loops that have a structure that the decider is capable of analysing well enough.

There are programs P where writing the correct decider takes some very hard maths, possibly beyond what we have now. On the borderline: I can easily write a program P where P(n) halts if n ≥ 0 and there are 0 < a < b < c such that $a^n + b^n = c^n$. Only quite recently there has been enough progress in maths to write a correct and very simple decider. (P will halt if and only if n = 1 or n = 2).

Note that a correct decider would have been possible without proving Fermat's last theorem. For example if someone had proved "there are no solutions with n ≥ 3 where a, b, c are co-prime and c > n^10000", that wouldn't prove Fermats Last Theorem, but would allow us to write a decider for the program P.

For many programs P, we can write a decider which halts on any input X, and tells us correctly whether P(X) halts or not. That is especially true for all programs with finite state. It is true for programs without loops, or with loops that have a structure that the decider is capable of analysing well enough.

An example: Let S be a state with a complete and discrete ordering and a smallest value. If S is initialised before the loop starts, and becomes smaller at each iteration of the loop, then the loop finishes and cannot stop P from halting. This allows to prove for example that the calculation of the big Ackermann function halts (in theory obviously. In practice the universe will be long gone before calculating A(4) would finish).

There are programs P where writing the correct decider takes some very hard maths, possibly beyond what we have now. On the borderline: I can easily write a program P where P(n) halts if n ≥ 0 and there are 0 < a < b < c such that $a^n + b^n = c^n$. Only quite recently there has been enough progress in maths to write a correct and very simple decider. (P will halt if and only if n = 1 or n = 2).

Note that a correct decider would have been possible without proving Fermat's last theorem. For example if someone had proved "there are no solutions with n ≥ 3 where a, b, c are co-prime and c > n^10000", that wouldn't prove Fermats Last Theorem, but would allow us to write a decider for the program P.

For many programs P, we can write a decider which halts on any input X, and tells us correctly whether P(X) halts or not. That is especially true for all programs with finite state. It is true for programs without loops, or with loops that have a structure that the decider is capable of analysing well enough.

There are programs P where writing the correct decider takes some very hard maths, possibly beyond what we have now. On the borderline: I can easily write a program P where P(n) halts if n ≥ 0 and there are 0 < a < b < c such that $a^n + b^n + c^n$. Only quite recently there has been enough progress in maths to write a correct and very simple decider. (P will halt if and only if n = 1 or n = 2).

Note that a correct decider would have been possible without proving Fermat's last theorem. For example if someone had proved "there are no solutions with where a, b, c are co-prime and c > n^10000", that wouldn't prove Fermats Last Theorem, but would allow us to write a decider for the program P.

For many programs P, we can write a decider which halts on any input X, and tells us correctly whether P(X) halts or not. That is especially true for all programs with finite state. It is true for programs without loops, or with loops that have a structure that the decider is capable of analysing well enough.

There are programs P where writing the correct decider takes some very hard maths, possibly beyond what we have now. On the borderline: I can easily write a program P where P(n) halts if n ≥ 0 and there are 0 < a < b < c such that $a^n + b^n = c^n$. Only quite recently there has been enough progress in maths to write a correct and very simple decider. (P will halt if and only if n = 1 or n = 2).

Note that a correct decider would have been possible without proving Fermat's last theorem. For example if someone had proved "there are no solutions with n ≥ 3 where a, b, c are co-prime and c > n^10000", that wouldn't prove Fermats Last Theorem, but would allow us to write a decider for the program P.