Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: nnymous109@gmail.com (nnymous109)
Newsgroups: comp.theory
Subject: Re: Yet another contribution to the P-NP question
Date: Thu, 3 Oct 2024 17:10:46 +0000
Organization: RetroBBS
Message-ID: <5a48e89d29b67daf45eee4e8af270e11@www.rocksolidbbs.com>
References: <85955d539da522cf777ab489101c0e2a@www.rocksolidbbs.com> <4b415dd5a91ac648bee8224fc3c28aa19706e06f.camel@gmail.com> <a4cacd3261a32cb9a769fbfe6ed1cd15@www.rocksolidbbs.com> <87cykqgfax.fsf@bsb.me.uk> <MWqdnZDONIeEjWv7nZ2dnZfqnPudnZ2d@brightview.co.uk> <877cawhg6g.fsf@bsb.me.uk> <793e0d649cf836d3b0bbdf9c1f946091@www.rocksolidbbs.com> <87v7yffh5h.fsf@bsb.me.uk> <3f36b24ff7a1d155688df8517ffc4032@www.rocksolidbbs.com> <87ed52f3q1.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: i2pn2.org;
	logging-data="417978"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="WGWI3FjRFxGJ6ITdWK0vrcDT1bUXKXnMN6DMEAZTkUA";
User-Agent: Rocksolid Light
X-Rslight-Site: $2y$10$ov3cc4M54klglidB9ptTJONShiHU9nLiYKHozSxSfW9YLN0hHnnWW
X-Rslight-Posting-User: 5809fff5c4fe67d6ec8559c4c0d41f9a0d5474cd
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 6552
Lines: 118

I apologize for the delay in writing this. I was in the process of
typing my reply when it occurred to me that I had not fully appreciated
what deciding a language using this scheme meant.

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

Indeed R does not decide anything, you would still have to use a machine
D to observe R and decide S. In the paper, note that we don't work with
P and NP at the start. Rather, we work with Pr.

If I may re-render your guess,

   s in S iff S.(R(s)) satisfies P1 = {q_accept}
   s not in S iff S.(R(s)) satisfies P2 = {q_reject}

But what we have instead is if S is in Pr, then

   f(t) in S iff S.(R(t)) satisfies P1 after it becomes stationary
   f(t) not in S iff S.(R(t)) and satisfies P2 after it becomes
stationary

where f is a computable surjection, the runtime of R is polynomially
bounded, and P1 and P2 are generalizations of {q_accept} and {q_reject}.

To decide that s is in S in the usual sense, we'd need a machine D to
enumerate inputs to R, observe what R satisfies at stationarity, compute
f, and then check for equality between the result of f and the input s.

This is more inefficient, but we have defined this so that we know that
R (and D) will always halt, and the relevant polynomial bound, anyway,
is on the runtime of R.

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


Now, here is why we no longer need to make that assertion.

Considering L_P again, remember that we've defined things so that

s is not in L_P <=> not A1 and not A2 and not A3 ...

where A1, A2, A3 ... are statements that are a priori undecided (and we
have a different set of such statements for every s).

If L_P was in Pr, then we could construct a D as above observing L_P and
deciding the left hand side.

But we may also construct E to decide the right hand side using D. We
have to decide A1, A2 and A3 "independently" because any outcome of
those statements is logically consistent with the inputs to E (i.e., say
there are a 100 of such statements and any 99 have been decided, it
would still mean that there was 1 that could be either true or false,
which means it's undecided).

Because the only other operations in E and D are string enumeration and
computing f, all of these takes place in the recursion that D observes,
and we set things up so that the number of operations to be performed
escapes any polynomial bound.



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

Of course, there might still be unjustified implicit assumptions I'm
making, but I feel it reads better now (and at least section 16 seems
clearer to me). I am also more confident about it, but again, I submit
everything to your judgement.

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

Thank you very much. I would be immensely grateful for any assistance
offered to me throughout this process. If there's a clearer and more
natural way to say the same things I'm saying, then I all for re-writing
the document.

Also, I have a new version of the document up where I insert a paragraph
between sections 15 and 16 (numbered 15.1) to explain what deciding a
language means in this context, and I have completely rewritten section
16 by building out what I sketched above in this reply.

I wouldn't call it a different argument, it's just that I now have a
reason for why the assertion is true (or at least, I think I do).

Thank you again for reading thus far.