Deutsch   English   Français   Italiano  
<00b5dad9473a86e602c8e4573322e814@www.rocksolidbbs.com>

View for Bookmarking (what is this?)
Look up another Usenet article

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: Mon, 30 Sep 2024 01:53:25 +0000
Organization: RetroBBS
Message-ID: <00b5dad9473a86e602c8e4573322e814@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="4083311"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="rrhMWBcDAx1rC5+om1CWMH+W6SvwsR4AkzPL9w80GDY";
User-Agent: Rocksolid Light
X-Rslight-Posting-User: 997a80a59f36bca0d6daf54c90c3284ff767f4d5
X-Rslight-Site: $2y$10$nghlN5PxXvQOzS0Kct7mRuvUrqaCxmou2MT9bvC2uQq1d6/eqsAOi
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 6856
Lines: 140

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.