The Halting Problem Problem

[j_j]

@Rob

I appreciate the clarity. You’re right that treating “the program really halts or not” as a settled fact, even when uncomputable, is a metaphysical commitment. I also respect your preference for locating mathematics in the lived, sensory, cost-laden world we actually inhabit.

Good to hear !

@Rob

That preference, though, is itself a metaphysical stance. Calling a program a “blurry pragmatic equivalence class of material computations” still requires the capacity to identify what counts as the same computation, distinguish it from others, and exclude what does not belong.

I understand that some people use the sign “metaphysics” for any chain of the signs that smells like an assertion. But I also — very much in the spirit of an absolute empiricism — reject that common assumption that a “meaning stuff” in “inside” the signs.

In this context, I mean that you and I use the sign “metaphysics” in different ways. The same fork can be used to stab food but also as a bookmark. I am using “metaphysics” pejoratively and as a rhetorical device to point inquiry back to the qualitative pragmatic world.

OK, the scenery is in place. Yes, we do indeed need to learn how to enact this pragmatic equivalence class. We learn to enact equivalence by learning to overlook differences that aren’t relevant.

I think the easiest example is handwritten digits.

I’m going to guess that you also see a pattern here. All the scribbles in each row are qualitatively different and yet all equivalent in the sense I am talking about, equivalent in terms of the usual role that such scribbles play in the world.

We’ve both been trained to recognize this or that scribble as useful for this or that role. It’s a bit like recognizing a weird metal thing as “obviously a fork.” Objects like algorithms are richer version of this. Basically we make sense of the world in “layers and layers” of role-playing chunks of “quality.” That’s my own spin on Plato. The world is not a senseless fume or torrent of chaotic sensation and feeling. It is a world of enduring things that show up as “one of those.”

[j_j]

@Rob

Those operations are not generated by sensory quality or computational cost; they are the conditions that make any such equivalence class possible in the first place.

We might agree more than you think. I interpret Plato’s unwritten doctrine “rashly and eccentrically” to point at the fundamental structure of the world. Basically the world is an articulated qualitative continuum. The world is chunks of quality. You don’t have chunks without quality. You never find quality that isn’t chunks.

I use almost vulgar and comical language to make a serious point because I consider this phenomenology rather than metaphysics. It is “lower” than science. It works from only what all conversation takes for granted.

But consider my point above. I do not expect what I wrote above to “signify” for you as it “signifies” for me. It’s a vague pointing, that you may or may not pursue.

[j_j]

@Rob

I’m noting that the frame does not escape the structure it presupposes. The world we inhabit is not something we have constrained. We do not know what consciousness, gravity, and energy are.

The world may be pre-theoretical to US, but the view that we are the only observers begs the metaphysical question.

My own “phenomenalism” explicitly includes non-human subjects, even aliens if they are out there.

I’d say we have fuzzy and blurry knowledge of the signs we use, but that we can always get a better or different grip on them. Philosophical research changes the meaning of signs, but only directly for the researching philosopher. Then he or she may try to point others at a new way of understanding them. This is difficult. A philosopher is a strange kind of poet who points at the unnoticed aspects of the world with sounds and marks.

One of the many names for my approach is “poetic positivism.” So I’m not a “shut up & calculate” guy. One of my motives is to defend the validity of nonverbal expressions as ways to “disclose” the world to others. Art is important and significant. But check your own experience to validate this claim.

So I am trying to reactivate “logical” positivism as dialogical positivism. An unmitigated empiricism is not afraid of atypical roles for chains of signs. Personally I’m fascinated by the richness of the umvelt. I want to point down into this richness, not away from it.

[j_j]

@Rob

I find it unsettling that so many people engaging in ‘philosophy’ (a presumably free pursuit of objectivity) prefer to take the Feynman position. We want to think and discover, but keep certain doors locked.
The 3 laws of thought do not demand that and remain unaccounted for. They in fact imply that thought itself is prior and fundamental.

As I see it, following Gadamer, “we are constituted by prejudice.” Each of us meets the moment expectantly, prejudicially, in terms of our past. We can’t help it. So I don’t mean “prejudice” in a moralistic way. I mean that we react this way to a sign rather than that way.

We are always already on the way, with a framing of the basic situation that we don’t see in ourselves but in the situation. I’m doing it right now, with my prejudice that prejudice is a fundamental ontological concept, roughly equivalent to subjectivity.

OK, so I think that something like thought is co-fundamental. The world ( reality) is “articulated,” but I suggest that “thought” is better understood in terms of chains of signs as things in the world among non-sign things. Even my “internal monologue” is a chain of imagined English signifiers.

Objects in the world show up for us as “unities,” as chunks of quality. Signs are special objects that play various roles like the numerals in the image above. Because objects are already “chunks” or “syntheses of quality,” they are “generalized signs.”

You mention accounting for “laws of thought.” As I see it, we can only point at what is genuinely fundamental. Explanations and accounts take what is fundamental for granted. The fundamental is the brute bottom basis of sense.

This relates to what I mean by “metaphysics.” I relate this word to speculation and explanation. Phenomenology (poetic positivism) doesn’t pretend to explain. It just points. Because its research topic is what we are already doing without noticing it.

[Rob]

Yes. We’re decidedly prejudiced. We have no choice but to unpack and understand according to the three laws of thought. Understanding is necessarily relational.

We can’t help but see chunks as unity. The number 1 has no identity apart from being distinguished in relation to other quantities. Only then can the boundary of exclusion allow us to understand what the number 1 is.

By “is,” I mean a real quantity conceptually, not empirically.
In my view, it is the three laws that provide ontological status. That status can be known or unknown. The three laws are prior to both and can describe both.

I take it a step further and ask if laws of ‘thought’ imply a necessary objective mind.

You’re right that we cannot KNOW. We are subjective, not omniscient. We operate by a necessary faith in logic as fundamental to existence.

Its difficult because its not as if our considerations are purely mathematical and amoral. Were not calculators. We’re persons pondering truth claims. The 3 laws are prior to mathematics and formal systems. I perceive that Touring and Gödel anticipated that.

The idea that empiricism is absolute and by implication that mind emerges from impersonal stuff, is an idea, not something gleaned empirically.

Empirical data and experience doesn’t impart knowledge. The data must be interpreted under the conscious light of the 3 laws.

And though we sort all this through various ‘ductive’ chains of reasoning. The 3 laws do not interact in a linear stream the way our subjective formal systems operate. They are co-present and simultaneous in operation. They constitute what can only be described as a trinitarian holism.

Perhaps this is the structure that we both intuit as ‘knowing’ what we both concede we do not and that formal systems cannot constrain.

Whether the ultimate nature of the structure is personal or impersonal is very interesting, but not precisely the point here. Pressing this closely into the heart of the matter is enough. Apart from omniscience, we cannot escape metaphysics.

[SophistiCat]

@j_j

@SophistiCat

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.

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.

Thinking more about this, I realized that there could be a finite number of distinct decider programs – as few as two – that partition the set of all programs. But you would still need to map each program to its decider, and if this mapping cannot be compressed into a finite set of instructions then you still don’t have a universal decider, in line with Turing.

Taking a page from Goedel, how about a program that does a brute-force search for contradictions in a sufficiently powerful formal system, such as Peano arithmetic? Within the same formal system there is no proof of consistency, and therefore we cannot prove whether the program will halt or not.

[SophistiCat]

@Banno

The machine halts or loops, both verifiable. Or it neither halts nor loops, which is unverifiable.

You seem to be saying that for every machine, we can verify whether it halts, which contradicts Turing’s result.

[Banno]

I was too quick.

There are three potential outcomes for a Turing machine. It might halt. It might loop. It might do neither.

Here’s an example of each:

• Halt: A machine that stops at the first step.
• Loop: A machine that moves to the right in the first step and to the left in the second.
• Neither: A machine that moves to the right at each step.

Note that in each of these cases we know which will occur. For these, there is no mystery. We know what will happen. We can classify these Turing machines. So we can “decide” for some Turing machines. There are decidable sub-classes of Turing Machines.

Notice that the outcome is “determined” by the code given the Turing machine. The outcome (halt / loop / neither) is a fact fixed by the machine’s transition table and input. Given a specific machine M and input w, there is exactly one truth about what that machine does on w — it’s not contingent or probabilistic. The computation trajectory is a mechanical unfolding of the rules; nothing indeterminate happens at any step.

Notice also the asymmetry between halting and continuing. That a machine halts is semi-decidable by simply running the machine. That a machine does not halt is not decidable by running the machine. Halting is semi-decidable by running the machine - once it stops, you know it halts, but if it hasn’t at step n, you can’t decide it never will.

The central issue, the one that is ambiguous in the OP, is the difference between what we might properly call determinacy and decidability. Turing machines are determinate. They are not all decidable. But some are.

In our standard use of Belief and Truth, something can be true and yet not believed, or believed and not true. A Turing machine halts or continues. If it halts, we are justified in believing that it halts. If it continues, at some step n we have no justification from the machine for either believing that it will halt or believing that it will continue. But we can nevertheless sometimes have justification, as in the case of the “move to the right” machine. The justification in that case isn’t coming from the machine’s run — it’s coming from an external proof about the machine’s structure, which is invariant: the position strictly increases, the state never revisits a halting configuration. So there are really three epistemic sources in play, not two. We can decide by reasoning about the transition table from outside the execution; or by running the machine and having it halt; or the third option, that no decision is available for a machine that has not yet halted. But it remains determinate that the machine will either halt, or it will not.

1. Metaphysically: every (M, w) pair determinately halts or doesn’t. No exceptions, no vagueness, no third option.
2. Epistemically: our access to which disjunct obtains is asymmetrical; guaranteed eventually on one side, not on the other.

The claim of the OP, that the Turing example has direct metaphysical implications, is too strong. The implications are an addition to the example. Turing machines supply a clean, rigorous instance of determinacy without guaranteed decidability.

If a machine halts, we can in principle verify this by running the machine. If a machine loops, we can verify this from outside the machine, by noting that it has returned to a previous configuration and so will repeat its actions indefinitely. If a machine neither halts nor loops, we might be able to verify this from outside the machine, as with the ‘move right forever’ case. But that this is not always possible is exactly the content of Turing’s result: there is no general method guaranteed to verify non-halting for every machine that hasn’t halted at n.

[j_j]

@SophistiCat

Thinking more about this, I realized that there could be a finite number of distinct decider programs – as few as two – that partition the set of all programs. But you would still need to map each program to its decider, and if this mapping cannot be compressed into a finite set of instructions then you still don’t have a universal decider, in line with Turing.

That’s a great point ! Yes, we can’t know which of the finite set of deciders would work, or we’d glue them together into a general decider.

This reminds me that in the book by Hartly Rogers ( which I am far from having digested ) that there are many many “analogues” of the halting problem. The “halting problem” is like the “Turing machine.” It’s just one of many ways to “say the same-ish thing.” Of course the method is proving the equivalence of these “avatars” of our situation.

[j_j]

@SophistiCat

Taking a page from Goedel, how about a program that does a brute-force search for contradictions in a sufficiently powerful formal system, such as Peano arithmetic? Within the same formal system there is no proof of consistency, and therefore we cannot prove whether the program will halt or not.

I think I follow you.

If we had a general decider, then we could use it on any particular contradiction hunting machine designed for a particular formal system. In a finite number of steps, we establish the consistency or not of that system.

====

Here’s another view on the situation. Let’s say that a general decider has n bits.

Maybe n > 10000000000000000000.

OK, but now we have an n -bit program that can tell us what much much larger programs will do.

For instance, our n -bit program can decide what programs of size 2^n will do, no problem.

Sort of following Chaitin, a general decider would contain way too much “information.” Many open problems about natural numbers can be phrased in terms of whether a particular search that climbs up the positive integers halts.

So a “general decider” compresses “all mathematical reality” into n bits. In other words, the structure of the prime numbers can be compressed into a single positive integer.

Put this way, it is not surprising that no such decider makes sense.

[j_j]

@Banno

Here’s an example of each:

• Halt: A machine that stops at the first step.
• Loop: A machine that moves to the right in the first step and to the left in the second.
• Neither: A machine that moves to the right at each step.

Note that in each of these cases we know which will occur. For these, there is no mystery. We know what will happen. We can classify these Turing machines. So we can “decide” for some Turing machines. There are decidable sub-classes of Turing Machines.

The last two cases are really the same. “Loop” is just a metaphor for non-termination.

The issue is also phrased in terms of “total functions.” We want the function to “return” and answer our question for every positive integer input.

We want to know whether we are wasting our time waiting around for an answer.

But yes, of course some programs are obviously total and some other programs are obviously not total.

[j_j]

@Banno

Notice that the outcome is “determined” by the code given the Turing machine. The outcome (halt / loop / neither) is a fact fixed by the machine’s transition table and input. Given a specific machine M and input w, there is exactly one truth about what that machine does on w — it’s not contingent or probabilistic. The computation trajectory is a mechanical unfolding of the rules; nothing indeterminate happens at any step.

Of course I relate to this intuition, but “fact” is a strong word for an idealization. A Turing machine is not an empirical entity. Actual computers have finite memory, finite input and output sizes. Program size, like the rest, is vaguely bounded above by the state of technology.

This “determinism” is also “ideal” in that we build actual computers to “play by the rules.”

You say a “mechanical unfolding of the rules” but “mechanical” is a metaphor here. “Rules” is where the normativity confesses itself.

But theoretically of course each step is determinate.

This is why I see total computable functions as something like the height of objectivity.

[j_j]

@Banno

Turing machines supply a clean, rigorous instance of determinacy without guaranteed decidability.

Because we can’t always decide (determine) which stepwise-determinate partial recursive functions are total, their relevance to us — in general — is indeterminate.

I understand the vague intuition that “the future is really implicitly already here.” I even grant that “halts or not” is on the edge of sense, not sense.

The pragmatic translation is "should I bother to wait around any longer ? "

The answer is : " in general, we just don’t know."

We can say this another way. “There either are or are not an infinity of pairs of twin primes.” We may not know, but we can take comfort in the “completed infinity” of “immaterial truthmakers” is “already out there.”

A “veil of fallible belief” obscures the timeless trans-empirical truth.

To me you sound like a mathematical platonist. We can be one another’s foils.

We see no “theoretical” reason that we can’t keeping adding 1 and climbing up a therefore “topless ladder.” This vague sense of “we are always able to go on” encourages some people to think of a crystalline immaterial ladder that is already completely “there” — somewhere…

[j_j]

@Banno

If a machine halts, we can in principle verify this by running the machine. If a machine loops, we can verify this from outside the machine, by noting that it has returned to a previous configuration and so will repeat its actions indefinitely.

I already covered this above. Machines with bounded memory are theoretically quite easy, basically for the reason you mention above. For actual computation, the problem is theoretically trivial but pragmatically intractable, because huge finite numbers already crush us in the real world.

TMs have infinite tapes. The information in memory can swell without limit without indicating failure to halt.

The issue here is infinity — which plugs in to the issue of time.

[Banno]

As you say, Turing machines have infinite tape, so of course they are an idealisation; that’s the point. It’s precisely what makes the mathematics exact. The idealisation isn’t a weakness, it is what makes the entailment exact - certainly not a vague intuition.

Nothing abut logical entailment requires time. The story is a tenseless mathematical one, not a tensed metaphysical one.

[j_j]

@Banno

As you say, Turing machines have infinite tape, so of course they are an idealisation; that’s the point. It’s precisely what makes the mathematics exact.

The letter “a” is already an “idealization.” The word “exact” is an “idealization.” So I do not object to “idealizations” in general.

I’d suggest that “good” algorithms ( total functions ) make mathematics exact. I can always compare two fractions to see which is greater. I can always check whether two numbers are twin primes. I can validate the claims of others in a way that depends on only a minimal sharing in the enacted social conventions that “are” typed tokens.

I might have hoped to have a total function that could validate whether a positive integer encodes a total function or not. It turns out that this idea “doesn’t make sense.”

You can say that a fraction whose square is 2 “does not exist.” You have peaked into the ether to find its absence. Or you can say the phrase “fraction whose square is 2” is something like nonsense that isn’t obviously nonsense.

The “good program that decides whether another program is good” is something like nonsense that isn’t obviously nonsense.

Compare these two claims.

“This program halts or doesn’t halt. Full stop.”

“This particular positive integer is either prime or composite. Full stop.”

There is an important difference here, which is easily ignored.

In the second case, I have an objective method, a total function, that can reliably settle the claim in a binary way.

In the first case, I do not. Yet the claim takes for granted a non-objective framing of the situation, ignoring the absence of an objective method for settling the claim at all.

The “binary framing” leaps into eternity, omitting the actual situation, which is indeterminate, precisely because we don’t have a method.

I don’t know yet whether a particular large number is prime, but I can theoretically find out in a finite number of steps. So the number “already being prime or not” is less of a leap.

A sufficiently huge number might not be testable for primality now or any time soon. So the statement that it is “prime or not” is objective in a fading-out merely theoretical sense, for now.

[Banno]

A surprisingly unclear reply.

I gather you grant proofs work for some non-halting machines. Did you drop the idea that infinity requires time?

Your analogy doesn’t appear to do what you want it to. We have a proof that there is no fraction whose square is 2, not the mere absence of a found instance. Calling halting bivalent “in the same way” doesn’t work; there is different in kind.

And why require a decision procedure, as opposed to a decision proof ? Especially since in your example of √2 we have a proof, not a procedure. Why is having a decision procedure a precondition for a predicate having a determinate truth value?

[j_j]

@Rob

We operate by a necessary faith in logic as fundamental to existence.

I would endorse a much softer version of this.

I enact the “blind faith” that the noises and marks I put in the world are “there” for others as “significant.”

Philosophers who “aren’t hearing me” might ask for a “proof” of this. They launch noises and marks at me, asking for a “proof” that we blindly enact this “faith” in being heard. They demonstrate what they doubt as they doubt.

Those who want a “proof” of the “external world” miss the pragmatic social-interpersonal core of proof. They express their autonomy. “I demand evidence.” This is great. But they speak this demand to the other who is radically presupposed, demanding from the other a “proof” that they speak to the other.

As many philosophers have pointed out, “logic” is a normative term. I “ought” to tell a coherent story. I “ought” to adjust that story when others offer me more coherent stories. At the very least, I “ought” to adjust my story when someone points out an especially gaping plot hole. Or a place where my story is suspicious fuzzy.

On the other hand, to be a person is to have the world and the words in this world from a point of view. God’s dictionary of “true and final meanings” is nowhere to be found. Yet many philosophers have acted, without making this explicit to themselves, as if they had access to this divine dictionary. “The word means to me what it means to God.” Let me be clear that atheists do this too. “God” is a metaphor here for the omniscient narrator who sits unprejudiced in the balcony, unstained by mortal life on the ambiguous stage of temporary fools who clash with others for a moment and vanish, replaced by others carrying mostly the same few “truths.” For these our actors leave stains behind. They pick up a chain of signs and find a new chain of signs that is almost like the first, at least in their eyes and ears.

Mathematics at its most computational and numerical is where we seem to find the minimum of ambiguity and confusion. To the degree that “logic” means a formal system, it too is concrete. But logic as linguistic and mixed with non-formal terms is no escape, in my view, from ambiguity. Indeed, the formalism can conceal the slippery poetry that gives it life in the world.

[j_j]

@Banno

I gather you grant proofs work for some non-halting machines. Did you drop the idea that infinity requires time?

Let’s zoom out. In the real world, we have only belief. “True” is an indicator of belief. Belief is primary, demonstrated primarily in non-verbal conduct but also through verbal conduct.

OK. So an informal proof convinces me. A formal proof convinces me if the formalism “paraphrases” my genuine reasoning in a useful way.

A program that checks a formal proof for correctness may have a bug in it.

A relatively operational approach to measuring certainty is to look at what people risk.

For instance, I am offered a million dollars now if I consent to a (practically) unbounded search over the rational numbers. If the search finds an \frac{m}{n} such that (\frac{m}{n})^2 = 2, then my right hand will be cut off. The algorithm is a simple brute force algorithm, inefficient but easy to understand. Perhaps we use a “jury” of 12 different computers. They all have to agree on the first “solution” to (\frac{m}{n})^2 = 2. Note that the search is ultimately bounded by available memory, but we can assume they have the resources of Google.

Do we take the money ? Well, I would take the money.

If you divorce math from the “stakes,” it loses its traction. We enact math in the world as primates who care.

[j_j]

@Banno

Your analogy doesn’t appear to do what you want it to. We have a proof that there is no fraction whose square is 2, not the mere absence of a found instance. Calling halting bivalent “in the same way” doesn’t work; there is different in kind.

We can understand the informal "\sqrt{2} " proof as convincing us that it is pointless ( or even absurd ) to look for positive integers p and q that satisfy p^2 = 2q^2.

Turing’s informal proof shows us the futility of hunting through all possible codes for a computable “halt or not” predicate. Such a predicate is “nonsense” like the fraction that squares to 2.

Both informal proofs appeal to other beliefs that may themselves have been established by informal proofs.

This is the similarity that I see, but perhaps I am not addressing your concern.