Re: Yet another contribution to the P-NP question

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?

>
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.

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?
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

Weird, but OK.  Substring seems to be rather weak, but maybe that's
important later on.
>

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)
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.

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}
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.
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*.
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 [*]
So, to decide L_P,

With the assertion** that any recursion that decides that a
computation satisfies some property necessarily yields at least one
element of the computation***, I am suggesting that it is easier to
check for inclusion in this set that it is to check for exclusion.
>
** - I should have liked to call this a proof, but everything I come up
with ends up being circular, so I took the assertion on its face (which
kind of feels like cheating). Indeed, this is where I most need
validation.

>
Yes, this might be a fatal flaw, but I am not yet sure there is even an
argument to be fatally flawed because I don't yet know what your central
term, "decides that a computation satisfies some property means".  This
would seem, at the very least, to require that both "recursions" /and/
properties be encoded.  How do you plan to do that?
>

And that's really the core of the idea. The definitions serve to handle
the technicalities that arise in the details, and to make sure that
existing concepts can be subsumed into the new scheme we have. If this
path doesn't sound promising, then it is unlikely that I have a proof
after all.

>
It might have a fatal "the only way to do X is Y" assumption in it.
>
But I have another question.  Why all the new terms?  Unless I am way
off-base with what I think you mean, all this can be written using the
accepted and familiar terminology of Turing machines.  If you simply
don't know enough about how to talk about TMs, I would be happy to help
you re-write what you are saying in more conventional language (time
permitting).
>

* - In my handwritten notes, I have this as some stylized left bracket.
I couldn't find what I was looking for when typing it out, so it became
the integral sign, but there's absolutely no relation with calculus.
>
>
*** - We can be even more restrictive with the assertion: the recursion
necessarily yields at least some substring of at least one element of
the computation.