nnymous109@gmail.com (nnymous109) writes:
On Sun, 29 Sep 2024 23:19:02 +0000, Ben Bacarisse wrote:
>
>
Tuples are finite. S.(M(x)) is an infinite sequence.
>
Ok, noted. Is it that it is a tuple whenever it is finite, but when that
constrained is relaxed and it is allowed to be a infinite, it is more
appropriate to call it a sequence?
Not really. The term tuple has been accepted as the way to talk about
finite ordered lists (pairs, triples, etc.). The term sequence has
always been used for infinite indexed... well... sequences.
More terminology... This is usually referred to as iteration. The map M
is iterated to generate the sequence s_i = M^i(x).
>
I see. I shall use iterations instead.
>
I hope you say a lot about what M can be because, left open, the result
might not be what we would want to call a computation! Presumably, your
M is the function that maps one TM configuration to the next, yes?
>
>
Yes, provided you're interpreting something like 'q_0 1 1 1 0' that I
would a call a string as just a TM configuration.
Yes. A TM configuration is the often seen as a tuple -- for example the
triple consisting of the tape, the head position (an index) and the
current state. You can represent that as a string, of course so that is
can be operated on by "iterations" -- i.e. another TM.
I don't see why you say "recurses over". M is a map from strings to
strings. But using the term is merely a bit confusing. I don't think
you are trying to say anything significant by using it.
Okay, would 'iterates over' be better?
Not for me. The problem word is "over". It is not the usual term for
the domain of a map, but it's not a daft term either. The problem is
just the reader will go "what does the author mean here if not simply
the domain of the mapping?".
What I'm trying to get is say we have some string
>
G = 0 q z 1 0 1 and z is not in U_M,
>
M can still act on G in the following manner: if M contains a rule that
'0 q e' should be transformed into '1 1 q_b' where e is the empty
string,
>
M(G) = 1 1 q_b z 1 0 1
OK. So "over" is hiding something. M is not a map from U_M* to U_M*.
That's messy and seems to be unnecessary. What is the problem in saying
that strings M maps? Why not simply allow M's domain to contain all the
string that it might "operate on"?
Weird, but OK. Substring seems to be rather weak, but maybe that's
important later on.
>
It allows us to extend things like halting.
I was talking about the details. They look clumsy to me. What you say
below is straightforward and obvious.
It allows us to extend things like halting. Say I build M using the
transition table of a Turing machine and at some point in the
computation, M^i(x) is 0 1 q_accept 1 1. Because we built M from a TM,
it will be the case that M^(i+1)(x) = M^i(x)
That's fine and not all surprising. This does not require the odd
detail that M's domain does include all the string it might be applied
to!
Then we can say that S.(M(x)) satisfies the property {q_accept} and
becomes stationary at iteration i to capture the same halting idea.
Yes, I can see you might want to do that. I suspect there will be a
simpler way to describe the properties you are interested in, but that's
not important right now.
With the assertion** that any recursion that decides that a
computation satisfies some property
>
What does that mean? So far we all we know is that a recursion (let's
call one R to save overusing the letter M) defines, for any string s, a
sequence R^i(s). What does it mean to say that R decides anything?
Explain what you mean with a simple trivial case. Don't jump right into
explaining what "decides that a computation satisfies some property"
means.
>
My guess: if a "recursion" is indeed the map from one TM configuration
to the next, then R decides membership of a set S like this:
>
s in S iff exists(i) such that R^i(s) = ...q_accept...
s not in S iff exists(i) such that R^i(s) = ...q_reject...
>
Is my guess right? If not, you need to say a lot more.
>
>
>
Okay, if I may re-render your guess using my terminology, we would have
>
s in S iff S.(R(s)) satisfies P1 = {q_accept}
s not in S iff S.(R(s)) satisfies P2 = {q_reject}
Fine. By the way, you don't need to name everything:
s in S iff S.(R(s)) satisfies {q_accept}
s not in S iff S.(R(s)) satisfies {q_reject}
though you really should make it clear that {q_accept} is not what it
appears -- a set containing a state -- it's a set containing a string of
length one.
which is almost correct except for three points
>
1) We need to specify that the property satisfaction takes place after
the computation has become stationary.
That is not part of your definition of "satisfies" but it will, of
course, follow from the fact that the result of your iterations are TM
configurations and they always become constant when that state is either
q_accept or q_reject.
If did not go off into your own notation, there would be no need to
worry about this being obvious.
2) Also, R need not be constructed from a TM or have q_accept or
q_reject in U_R (i.e., in the set it "recurses" over), so P1 and P2 need
only be two properties that a computation cannot both satisfy at the
same time when it is stationary*.
OK. You've lost me. I thought R (and iteration) was always a TM
configuration transition function.
This must be cleared up, because non-computable maps are going to take
you into all kinds of murky waters.
3) And R need not act on S directly, we only need a surjective function,
f, to map strings that R can "recurse" over, that is from (U_R)* to some
superset of S [*]
Again you've lost me. I no longer know what it means for an iteration
(what was a recursion) to decided something.
So, to decide L_P,
Ah, this sudden stop made me go look to see of there was another post.
And there is, and it suggests you plan to offer a different argument. I
hope I have not wasted my time here.
-- Ben. 
…