On 12/05/2022 19:30, Ben wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>
>> On 12/05/2022 15:02, Ben wrote:
>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>
>>>> You could think of a TM as a DFA that's been functionally enhanced to
>>>> allow at each computation step
>>>> i) left/right (single) stepping of its input tape head
>>>> ii) rewriting of the symbol under the tape head whereas a DFA is
>>>> restricted to work with strictly right stepping of its "input tape
>>>> head" so it only sees each character once (and so no concept of
>>>> rewriting anything because it couldn't be reread anyway).
>>> Though one used to talk about "transducer" DFAs where each edge of the
>>> graph also had an output symbol. This was not "written" anywhere but
>>> the result was the concatenation of output after processing the input.
>>> <cut>
>>>> A) The DFA/TM termination conditions are a bit different. A DFA halts
>>>> naturally at the end of the input string, so it's fine (and typical)
>>>> to have accept/reject states that are entered multiple times during a
>>>> computation, i.e. those states aren't "final" states in the TM sense.
>>>> A TM clearly needs some other way to explicitly indicate it's
>>>> finished. Typically (e.g. Linz) some TM states are designated "final"
>>>> states that halt the TM - if it has accept/reject states those are
>>>> final, so can only be entered once.
>>> This is, as you say, typical. But it's horrid! Almost every author
>>> seems to copy this ancient idea, but there's no need for the
>>> complication. A TM halts "naturally" when in a state that has no
>>> defined transition for the current input.
>>
>> From a programming perspective, I can see how that's a bit more
>> convenient, but I don't like the idea that much - e.g. with an
>> explicit halt state we can see it clearly on the state transition
>> diagram (as one of the destination circles pointed to by arrows). The
>> alternative is having to inspect all the circles and identify those
>> which are lacking some transition rule - that's lacking transparency
>> in my opinion.
>>
>> (And if I identify such a state missing one or more arrows, am I to
>> assume that's deliberate to create a halt condition, or does the
>> author simply know that those conditions will never arise during
>> execution, and was being "lazy"?)
>
> When reasoning about termination, you have to consider halting in
> non-final states, so I don't think it matters much.
>
>> So I'm thinking that an explicit halt state is maybe the most
>> (conceptually) logical way to do it, and I like "conceptually
>> logical". To me the "no defined transition rule" seems like a kind of
>> hack invented by a programmer to save a few lines of code! (I've
>> nothing against programmers of course, and if you teach people to
>> program TM simulators, I can see the appeal of the idea.)
>>
>>> If you want and accept/reject
>>> notion, then one can use a simple convention that the TM accepts if it
>>> halts in a state with no defined transitions at all, but rejects if it
>>> halts in state with defined transitions, none of which apply for the
>>> current input.
>>
>> That seems (conceptually) awful to me! I mean, where's the /logic/ in
>> that, beyond making the programming task well defined for someone
>> building a TM simulator?
>
> The logic here that you have to consider the one case anyway (halting
> because of no defined transition) and the second case is as explicit as
> you'd like -- a state with no out-going arrows. You can even agree to
> draw double circles of these.

(ok, but I don't like the "halt because of missing rule" idea either! :) )

>
>> Perhaps if I were more bold I might suggest your perspective could be
>> overly shaped by your day to day job experience of teaching the
>> /simulation/ side of the subject... :)
>
> That's possible. Though one almost always just does this as a sketch.
> The full details of a UTM are messy and don't really add much.
>
>> For me, TMs are /mathematical/ constructs, used to discuss the nature
>> of computation and limits of algorithms etc.. So naturally I like
>> logical mathematical definitions. For me, the weighting (out of 10)
>> I'd apply to "making a programmer's job easier when coding a TM
>> simulator" would be 0. I mean, it's not /that/ hard whichever way we
>> go.
>
> I don't see it like that at all. The reasoning about TMs is not made
> any easier by the usual definitions unless, possibly, you insist that
> the state transition function always maps every member of the tape
> alphabet.

I'd be ok with insisting that the function is complete rather than partial. Actually, that seems
mathematically most "natural" to me, but I get that it's a /pain/ for a TM programmer, so an
emulator design could relax that requiremnent.

But mainly my point was just that I feel (my preference) is for halting to be totally explicit,
rather than a kind of default/fall back when no transition rule is found. A consequence is that NOT
having a transition rule to apply must simply be not allowed. [Either the transition map is
complete, or in the case of a practical TM simulator it's the TM builder's responsibility to always
have a rule when not in a final state.]

It's not to do with ease of use, but just my desire for the TM definition to match my intuition of
"algorithm" as closely as it can. That intuition is basically the (ancient, pre-TM) flow-chart
which in TM terms becomes the state transition graph, and it seems more natural to have a "STOP"
box, like in a flow-chart. If a flow-chart led to a box that had no arrows readers would say
WTF???, not think "aha, that must mean I've reached the end". But all this is just my preference,
no big deal. Of course I understand they're all equivalent mathematically.

>
>>> A few people prefer not to bother with accepting and rejecting states at
>>> all, but instead just use the resulting tape. For example, the TM is
>>> deemed to have rejected the input if the tape is empty (i.e. contains no
>>> non-blank symbols).
>>
>> Isn't there a problem here, in that now we can't actually tell when a
>> computation is finished? Say after 10^234829873473829 steps no output
>> has been written - what does that signify? OK, "nothing" is an
>> answer, but then is this actually in line with our original intuitions
>> which were concerning /finite/ algorithms? This is a bit more like
>> when TMs are /acceptors/ (recognisers?) rather than deciders, but even
>> then, if a non-blank is written to the tape, it could be subsequently
>> blanked out again, so its not really like an acceptor.
>
> I don't see what you are getting at. How is this different with
> explicit final states?

Um, at this point I thought you were suggesting the TMs /didn't/ halt, but somehow just used what
was written to the tape to indicate accept/reject!! See final remalks.

>
> There's no "we watch and see" here because, as you say, TMs are
> mathematical constructs and a TM/input pair either denotes a finite
> sequence of configurations or it does not.
>
>> Perhaps something like "accept if 0 is ever written to the tape,
>> reject if 1 is ever written"? That would logially work I guess.
>
> That would be weird.

Agreed! (at this point I was under a misapprehension - see final remarks.)

>
>> OK it's only now occured to me that you didn't say "..not to bother
>> with *final* states.." or "..not to bother with *halting*..". So I'm
>> sure you meant having some explicit HALT action, followed by checking
>> the tape to distinguish the halting reason - which makes perfect
>> sense, and is maybe how I would have invented TMs (Terry-machines of
>> course) :)
>
> I'm not sure I follow. Maybe you do see what I'm getting at? A
> decider, D, for a set, L(D), is a TM that always halts. It therefore
> computes a total function f_D: Σ* -> Σ*. The accept/reject notion is
> just a convention that can just as easily be defined as f_D(s) = ""
> (say). Similarly, a recogniser computes a partial function.
>
> This is independent of the issue of how and when a TM halts, but my
> preference is for both my suggestions.

I do see what you're getting at. You were NOT saying that all TMs would by implication never
terminate. (Duh, lol)

You were saying that the decider TM terminates [by some agreed mechanism, even though it has no
accept/reject states], and then we have to specify how we will interpret accept vs reject haltings -
which can readily be done through what is finally on the tape. No problem - that's what my final
paragraph was concluding.

The problem was I DIDN'T read what you said that way at first, and so had written a couple of
paragraphs on a faulty basis. So my fault for misreading, and also for not going back and rewriting
what I'd said before.

WHY would I think you were saying such a bizarre thing?? Well, in Linz (&similar), deciders have
two final states, accept/reject, and I misinterpreted your "A few people prefer not to bother with
accepting and rejecting states at all, but instead just use the resulting tape" as saying the TMs
never halted [they have no remaining final states!] but just use the tape to indicate their decision
somehow. My mistake...

Mike.