What Does Halting Mean

Let's dig away at that ol' GeneralHaltingProblem a little further.

Our young friend Turing has a train set with a very, very, very long (unbounded length, to be precise) track. He has a clever little train to put on that very long track. It can read and write numbers on the sleepers on the track. And it has a teeny little FiniteStateMachine that tells it when to read, when to write, when to go forward, and when to go backward, depending on a combination of its current state and the digit on the sleeper its engine sits on right now.

Question Number One: Turing easily showed that the FiniteStateMachine itself can be encoded on the track. But it's an infinite track, so it can encode an InfiniteStateMachine. The GeneralHaltingProblem statement is usually regarded as concerning itself with finite representations of machines P and Q. If we extend it to infinite representations of P and Q, then WhatDoesHaltingMean?

Hmm. That's a curious question. But this is a very curious train set Turing has in his Christmas stocking, and curiouser still how many people have bought the same set for their kiddies without considering all those other toys in kindly old Mr Cantor's toystore.

Sometimes Turing's train enters the "halt state". You might think that means it's powered down, turned off, dead. But when the states are encoded on the track as Turing suggests, then a "halt state" means the train just sits still reading the same spot over and over again. It's not powered down, though it's obviously not going any place. Still I'd say it's halted - wouldn't you?

And sometimes Turing's train chugs up and down the tracks repeating the same behavior over and over again. It's in a cycle, an InfiniteLoop over the same finite set of sleepers. From the point of view of all the other sleepers that it doesn't visit in its loop, it may as well have halted.

Furthermore, if we applied Turing's definition of a "square" (a finite segment of the track encoding a symbol) to fit this cycle - then this is obviously equivalent to a "halt state". Doing this redefinition is officially legit by Turing - he did it himself to turn multi-symbol tracks into binary tracks. And you can do it in reverse - think of the amoebae and still tinier quantum odiosity zipping and zapping through a halted train. Halting has to do with confinement to discrete places on the track, not with some pernickety movements inside one or another discrete place.

Question Number Two: following the reasoning above, allowing that any cycle in the train's behavior is equivalent to a halt-state, what can we say of a train that cycles through a truly InfiniteLoop - one that visits an infinite subsegment of the infinite track repeating the same behavior over and over and over again? Reversing this, as Turing did, can we not regard any single square as infinitely subdivisible, and say any train whose motion is bounded to this square is in fact cycling through an infinite loop?

We could then say that a train that never repeats the same behavior has in fact halted. Or if we deny it, then we'd have to say that we can't infinitely subdivide the square of the track that a train has halted on. But Turing asserted that any symbol set can be reduced to binary by covering a larger set of subdivisions of the track, and doing this is essential to the representation of number itself ... oh dear, it seems the definition of halting may be inconsistent!

Certainly, an argument like that would not have troubled our kindly old toy-store owner, Mr Cantor. He was very fond of a game called Diagonalization, which is something like "Snakes 'n Ladders", but on an infinite board. Nor would all this have troubled Cantor's neighbors, the elderly Mr Fraenkel and another retired gentleman living under the name of Zermelo. All three of them spent their dotage arguing with each other about the previously mundane matter of fractional street numbers ... but that's another story.

-- PeterMerel

If a loop has an infinite number of steps, then it is not a loop.

-- MichaelSparks

Begging your question, but having here in my topological pocket an infinitely stretchable rubber band, how far will you permit me to stretch it before you'll assert it breaks? Point being that infinite subdivisibility of an interval or a loop doesn't affect its topological class.

Strikes me that there's something vaguely fishy about this argument. Not that I'm here to defend the Turing machine, just digging into the argument in my own way, if that's acceptable.

There seems to be mixing and matching of levels of description without notice or reason given, in order to allow things that aren't required.

Firstly, the image of a train on a track invites us to imagine the "head" of the Turing machine as a practical device, with some mechanism inside it that implements the state machine. And indeed this can and has been done. But the Turing machine as such is a mathematical construct not a device.

I have not suggested that a Turing machine is a practical device.

No, you haven't. Nor did I claim that you had. But I do claim in producing the image of a train, and then later talking about amoebae within it, you're inviting your readers to think about results regarding a mathematical structure by drawing analogies about a practical device. A hazardous business, no?

Turing's model represents an appeal to intuition concerning human computation. By poking at the frame of that appeal we may find ways to break or bend it.

For example, regard the space of all possible tape configurations achievable of any FSM-based ATM as a set of numbers. By Goedel it is provable that there exist numbers - tape configurations - that are not members of this set. Goedel provides a diagonal means of constructing one of these. So demonstrably a human is capable of a calculation that no ATM can perform. Goedel shows Turing's appeal to intuition must be broken.

Well, suppose it were a practical device, then why is there any necessity that the mechanism should not switch itself off after entering the halt state? One could imagine the mechanism constructed in such a way that it did enter a micro-loop of the sort described, but where's the necessity?

The question is, WhatDoesHaltingMean? You may say halting just means the r/w head enters a state of its FSM and then, who cares, the model ceases to be relevant. But such cessation is defined outside the model. So ignoring the question doesn't help; the model remains. Certainly you can't dispense with the model and prove anything.

And anyway, as far as I know (any contrary reference will be followed up with pleasure), there's no necessity for the mathematical Turing machine to go into a "read-do nothing-read" loop, either. Doesn't halting mean to enter a combination of head state and tape symbol for which there is no subsequent action to take, of any kind? That's a what modern presentations of Turing machines that I've seen suggest, anyway.

Then farewell "halting" - your model is no longer rich enough to describe the halting/non-halting distinction. The Turing/Post model isn't just a bit tacked on to the HaltingProblem for fun, you see. It's fundamentally necessary to the frame of the proof - throw it out and you have no way to represent the behaviour of an FSM, much less introspect same.

To be precise about the model definition of halting I refer to Turing's 1936 paper at http://www.abelard.org/turpap2/tp2-ie.asp: "A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind."

And I refer you right back to it. "A machine will be circular if it reaches a configuration from which there is no possible move", so there doesn't seem to be any necessity to one of the planks of your argument.

'The fact that the machine does not move outside its terminal square tells us nothing about its movements within that square. What's more, by ZenosParadox? of motion, I can show that no matter how tiny the squares there is room inside for the head to move around. Unless you define the squares as points - but then moving from one to an adjacent becomes problematic indeed. You really can't have your cake and eat it here - Turing's model admits an exploitable ambiguity, and no model, no proof.''

But, you say, the tape might have bit sequences on it representing other symbols, then the micro-loop version of halting means repeatedly traversing the bit sequence that represents the higher level symbol that's at the halting position. Why? Why would such a micro-loop not be content with re-reading the last bit of the sequence representing the last symbol? This suggests to me that the dynamic halted state you refer to doesn't need to cover more than one square. Again, it could, but doesn't need to.

The question is purely to do with the significance of the one square, however defined. WhatsaDistinction between a machine that chugs around inside one bounded region of the tape, which you're pleased to label a single square, and another region which I'm pleased to label with multiple squares? By Turing's definition, there seems to be no clear distinction.

Secondly, even if we agree that halting will mean repeatedly traversing the bit sequence that represents the last high-level symbol read, how does it follow from this that any one bit on the tape can be expanded?

Again to quote Turing's '36 paper: "It is always possible to use sequences of symbols in the place of single symbols."

To replace the high-level symbols with bit sequences is pretty much decompression. The higher-level symbols will have more points in their parameter space than are used, thus they can be decompressed by, for instance, labeling the points that are used with unique integers and using the binary expansion of those as their representation on the tape. This is fine, but introduces an intermediate level of denotation between what's on the tape and the problem set up by the programmer. That's fine too, so long as you know that's what you're doing.

But the parameter space of bits only has two points, both already occupied by bits, so there's no representation to decompress them into. That doesn't stop you forcing a bunch of new information into invented sub-states of the halt state, I suppose -

The point is that by Turing's explicit construction you're permitted to do this.

Sure you are. I'm suggesting though, that maybe replacing a single bit with a sequence of other symbols is an operation of a different kind from replacing another symbol with a sequence of bits. I might be wrong. But feel free to dismiss rather than discuss.

Oh dear, I feel a model patch coming on. Let me guess: an operation of the first kind is a way to construct a class of symbols, where an operation of the second kind is a way to construct a set of symbols ...

I suspect that it is possible to simplify a lot of the reasoning above by realizing that any Turing machine that halts does so after looking only at a finite portion of the tape. Moreover, every Turing machine that looks only at a finite portion of the tape must either halt or loop! The reason for this latter claim is that the number of symbols is finite, the number of positions on the tape is finite, and the number of states in the machine is also finite. Therefore, the total number of states of the whole system is also finite, because each system state can be represented by the entire contents of the tape, together with the current position on the tape and the current state of the machine.

Therefore, asking whether a given machine halts is equivalent to asking whether it is possible to put a finite upper bound on the amount of tape that the machine uses.

-- AndrewKoenig

I'm afraid this is incorrect. Even with an alphabet of just 3 symbols - a finite portion of the tape of just 3 squares, if you like - it is possible to construct a sequence of movements of the machine that never repeats - http://www.americanscientist.org/template/AssetDetail/assetid/14405/page/5. Now it isn't possible to do that with an FSM ... but that's cool, like we observed above, there are plenty trajectories over the tape that FSMs aren't capable of emulating.

Re Question 1: Only a finite part of the track is ever covered with non-blanks. The rest is space to be allocated on demand. Therefore, there can be no encoding of an infinite state machine on the track. The question is moot.

I dig this. --Pete.

Re Question 2: A train that repeats the same behaviour over and over may be considered halted. This is purely a matter of convention and any notion of halting can be converted into any other by adding some suitable states to the state machine. What is definitely different from being halted, is a train that does something to the track and needs an ever growing segment of the track to do so. This is no loop, no state ever repeats and if there's an end to this cannot be said for sure. Turing wasn't really talking about infinite loops, he was talking about incomprehensible processes on the track.

I dig this too. It's the distinction between contractive and expansive process. Thanks for the clarity. --Pete.

Re Question 2b: No, you cannot infinitely subdivide anything. A Turing machine runs in discrete steps. You can subdivide if you expect some gain from it, but not indefinitely. After subdivision, you still have discrete cells on the track and you still have discrete steps.

I expect no qualitative change with subdivision. But your 2a answers anyway. --Pete.

CategoryDiscussion