The Halting Problem Problem

Logic & Philosophy of Mathematics
1

“Does a program halt on a given input ?” I would like to react to this question as a sort-of-constructivist.

Turing machines are great, but they are one model of computation among many “equivalent” models. It suffices to think of a program written in C or Python, except that we idealize the concrete situation by abstracting from the materiality, cost, and finitude of concrete calculation.

We can specify our program further. It is provided with an positive integer input, and then we hope that after a certain number of discrete steps that it will return a positive integer output. We further idealize the situation by allowing arbitrarily large integers in both cases.

We understand that some programs fall into infinite loops. We can easily create such programs. We “know” with practical certainty that the program will never return an output.

We also know that some programs will obviously always return an output. We can easily create simple programs that do this. For instance, it is trivial to write a constant function that always returns 0.

These are the extreme cases. “Of course” the program will halt, terminate, return. And “obviously” the program will loop forever.

What about the difficult cases ? The program is huge. Note that we do not limit the size or complexity of programs in this model. We also understand that some programs need an astronomical number of steps to complete their task. Many crucial cryptographic systems are vulnerable to brute force. Try every key ! But there are too many keys for that to be likely to work in the real world. Still, the time we expect to have to wait is bounded above on actual ( finite ) computers. With Turing machines, which are infinite in terms of memory, there is no upper bound on the steps a good program may need to complete its task.

Now consider a massive randomly generated program, much larger than MacOS. Does this program halt on an input of 0 ?

Turing showed that we have no method — no single program that always returns an answer — that can answer this question for us.

I suggest that Turing’s result be interpreted as throwing into question the predicate of “halts or not.”

The “platonist” will likely say that “it does in fact halt or not” but we can’t know the truth. The truth is out there. The predicate “halts or not” is semantically secure. The issue is epistemic.

I call this dominant position “platonistic” because it abstracts away from time. For the “platonist,” time is not real.

What’s the alternative ? The program has not already halted-or-not “in eternity.” Instead mathematical reality is “in progress.” We have “certain that it halts” and “certain that it loops” and “currently indeterminate.” The situation might crystallize.

The problem with the halting problem for the quasi-constructivist is that it takes a metaphysics for granted. Uncomputable predicates are at the fuzzy limit of sense, where objectivity fades out.

3 Likes
2

What other model of computations are you thinking of? Could you list and explain some of them?

Any code samples in C or pascal or Python language coding perhaps?

3

A program can read input continuously or one at a time. It really depends on how the coding is done. Not sure how Turing machine coding would be. If coding for some Turing machine routine execution is available, we could look into further?

4

Let me share a link to give you a sense of how many there are. And we can easily come up with many more.

My current personal favorite is

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation. Markov algorithms are named after the Soviet mathematician Andrey Markov, Jr.

I wrote up some notes on these here.

My twist on Markov machines has a Turing flavor.

The basic idea is that you make up rules for replacing one group of symbols with another.

On a philosophical level, all that matters is that the model of computation is of “maximum power.” There are lower power models like DFAs.

In my view, all actual computation in the world is finite. So models of computation are great but they “lie” in a useful way through ignoring limitations on memory, energy, and time.

For instance, I don’t have 3000 years to wait for the program to return an answer to my question. I also can only set up so much “physical stuff” to function as memory. Finally it take energy to push actual computations along. Real computation “costs” and is always finite.

5

Yes. So you are missing some background here. Any finite amount of information can be squeezed into a single positive integer. Likewise a single positive number output can return any finite amount of information.

If you study the theory, you end up understanding the “equivalence” of all of the ways to modeling computation. It then becomes a matter of aesthetics and utility. It’s easier to prove things about the simpler versions. Since the simpler versions are equivalent, you are proving things about the messier versions at the same time. “Simple” and “messy” describe how intuitive a model is. Theoretically they all have the same “power.” I am assuming here that we are talking about those with the “full power” of a Turing machine.

6

The same Platonist assumption haunts the hard problem of consciousness.

We are

1 Like
7

Let me know if the Markov pdf makes sense to you. I can send you a link to an emulator written in Javascript.

Here’s only the first part of a recursive calculation of the seventh Fibonacci number:

f|||||||
g|||||||
h|||||||
OO|i||||||
OO||i|||||
OO|||i||||
OO||||i|||
OO|||||i||
OO||||||i|
OO|||||||i
OO|||||||jO
OO||||||j|O
OO|||||j||O
OO||||j|||O
OO|||j||||O
OO||j|||||O
OO|j||||||O
O|Ok||||||O
O|O|k|||||O
O|O||k||||O
O|O|||k|||O
O|O||||k||O
O|O|||||k|O
O|O||||||kO
O|O||||||jO|
O|O|||||j|O|
O|O||||j||O|
O|O|||j|||O|
O|O||j||||O|
O|O|j|||||O|
O||Ok|||||O|
O||O|k||||O|

Each row of symbols is an “instant” of the computation.

This is an example of a program in “tape machine language” — my version of the “Markov machine.”

g || > h ||
g | > |
h | > OO| i
i | > | i
i > j O
O| j > |O k
| j > j |
k | > | k
k O > j O|
O j > m
| m > m |
O m > O x
x | > y
y | > | y
y O > O z
z || > a
| a > a |
O a > b f
| b > b |
O b > f
f ||| > g |||
f || > | f |
f | > |
f > |

Do you see how this language is brutally simple ? Each row is a “substring replacement rule.” The order of the rules matters. You use the first rule you can from the top. Repeat. If no rule applies, you are done. The final string is your return value, your output.

All computation is “theoretically reducible” to this language. Of course richer languages are far easier to program in.

8

Perhaps I have not fully understood your point, but it seems to me that Gödel’s incompleteness theorem partly addresses this question. It shows that in any sufficiently expressive, consistent formal system, there are true statements that cannot be proved within that system.

You write that, in some cases, we cannot determine whether a computation will ever return a result. But it seems to me that this demonstrates a limitation of our formal methods rather than the indeterminacy of the answer itself. Physical time does not, strictly speaking, enter into the mathematical formulation; computation is represented as a sequence of discrete steps.

Moreover, a particular problem may perhaps be solved by another method or within a stronger formal system based on additional axioms, even though Turing showed that no single algorithm can decide the halting question in every possible case. So I do not quite understand why the absence of a universal method should imply that the predicate “halts or does not halt” is itself indeterminate, rather than that its truth is inaccessible to us or undecidable within a particular formal system.

2 Likes
9

I hope you will excuse a small digression. I have a question about Turing’s result: Does it imply that there are programs whose halting status is in-principle undecidable? Or could it be that for every program, there is a method (a program) to establish its halting status? Of course, to satisfy Turing’s result there would have to be an infinite number of such programs, otherwise a single program could be cobbled together from a finite number of methods. But that would still be weaker than an outright no-go.

1 Like
10

Right. So what do we mean by a “true” statement ?

We have an informal proof that the formal analogue of “this statement has no formal proof” has no formal proof in the formal systems that matter to us.

In other words, we believe that there are assertions we believe whose “formal analogues” cannot be proved in a formal way.

But what is this mathematical "truth " ? The word often “reads” in a way that takes mathematical platonism and the unreality of time for granted.

I think the cautious approach is to say that we have strong consensus of belief. No one with any mathematical sense looks for a fraction \frac{p}{q} such that (\frac{p}{q})^2 = 2.

How can we unpack this ? I’d say that human beings enact this understanding by not wasting time on the unbounded search for such a \frac{p}{q}. The futility of such a search is recognized through the informal proof that there is no such fraction.

11

So you quite reasonably express here the dominant mathematical platonism, which “speaks from eternity.”

Note that computation is idealized here. A cautious understanding of an algorithm is as an equivalence of various concrete calculations. I can use pencil and paper or an electronic calculator or even one of the early mechanical computers to see if 153 is prime.

The outputs of actual computations are also some kind of “sensory numeral.” I react to shapes like “3” by moving my body in the world. We know from Saussure that the “positive element” doesn’t matter. A different shape could work like a “3”. The king in Chess might be made out of wood or plastic, shaped in various ways. What matters is the “enacted role” in social pragmatic technological life of an arbitrary sensory-physical signifier. It’s the independence of the role from any particular arbitrary numeral that gives rise to the perceived “immateriality” of numbers. I’m saying that Saussure and Goodman and Sellars help us finally understand this elusive “immateriality.”

I think it’s worth noting that all actual discrete computers are finite. If we restrict the size of inputs, outputs, and computer memory, then we no longer have the halting problem.

This is because we end up a finite number of states. We can check for a loop theoretically, by a huge but finite search.

I say “theoretically” because even finite numbers can be too much for actual computers.

12

I’m saying that “halts or not” is where objectivity and sense break down or fall apart.

Let me offer some contrast. “Prime or not” is a computable predicate. For any particular number, I can determine via a program that always halt, where it is prime. I can even define primality extremely “objectively” in terms of such an algorithm. We might even use the most obvious but inefficient one. Try to divide n by every number d such that 2 \le d < n. If we find such a d then n is composite. If we complete the search without finding d, then n is prime.

Turing showed that “is the number of a program that halts on every input” does not have this kind of “objective decision program.” For some, this verges on the mystical. For others, this reveals that there’s something fishy in our approach to the “already completed infinite set.”

The issue is “only” theoretical or aesthetic, because actual computation is finite. It’s modeled by a DFA where we also limit the size of the input. So it’s “less than” a DFA. Of course these days our programs and input sizes are more than huge enough to stagger us. The finite is theoretically easy but already pragmatically overwhelming.

13

Yes. For brevity and clarity, let’s call a program “good” if it halts on each of its inputs. A program is “bad” if it fails to halt on at least one input.

Now we can say that there is no good program that decides whether any particular program is good.

Here’s my paraphrase of the most beautiful and compact proof he gives in his famous paper.

If we had a good program that could do this, then we could prove that there are an “uncountable” number of good programs. In other words, we show that any list of good programs leaves out a good program, namely the “diagonal” good program.

This is absurd because it is trivial to enumerate all programs, both good and bad.

That’s a great question. I don’t know. I agree with your reasoning. I love this stuff, but I didn’t specialize in it. Perhaps a specialist can jump in on this.

As you may already know, the calculation of busy beaver numbers requires tailored/specialized proofs that this or that particular machine halts.

1 Like
14

Yes indeed !

Interesting that the same Wittgenstein who gave us “pure realism” in the TLP was extremely invested in his philosophy of math, which is largely neglected. Many mathematicians dislike Wittgenstein’s philosophy of math, for obvious reasons. It brings math down to earth, reduces its mystique. But arguably makes it more beautiful as more “real” in the sense of lived in time.

15

I see no metaphysical implications here, just three outcomes, only two of which are verifiable. The machine halts or loops, both verifiable. Or it neither halts nor loops, which is unverifiable. The situation remains binary. There just are some Turing machines that never stop, and never loop, but we can’t decide which they are.

16

That is a metaphysical statement that asserts determinate facts exist even when they’re uncomputable and unverifiable. Saying we can’t decide which they are doesn’t remove that assumption.

I don’t have a problem with it because your position that determinate facts exist assumes Identity, distinction, and exclusion. I just don’t understand the unwillingness to concede that those 3 fundamental laws (though Trinitarian) are metaphysical and ontological priors.

17

That’s not a metaphysical commitment. It’s an entailment of the description of a Turing Machine. That there are Turing Machines that do not halt is a consequence of the description of a Turing Machine, not an added bit of metaphysics.

18

Every description identifies, distinguishes, and excludes. How do you account for those laws that enable coherent description?

19

Might be best if you kept your theology out of other threads.

20

Might be best if you don’t publicly and blatantly pretend I didn’t ask a legitimate question. Your philosophy of materialism is no more relevant to the question than my philosophy of theism. The question remains.

How do you account for the 3 laws that are known to be and accepted as metaphysical?