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 19:02:08 +0000
Organization: RetroBBS
Message-ID: <3bd02cd374e5acd6ddde87ad44efa23a@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> <00b5dad9473a86e602c8e4573322e814@www.rocksolidbbs.com> <87wmisekg6.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="430235"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="WGWI3FjRFxGJ6ITdWK0vrcDT1bUXKXnMN6DMEAZTkUA";
User-Agent: Rocksolid Light
X-Rslight-Posting-User: 5809fff5c4fe67d6ec8559c4c0d41f9a0d5474cd
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Rslight-Site: $2y$10$w2ZdeWAkFHUed5AYChzs8.X9aAZbS1v1.CLmGUWRgcAte0/tr5/Q2
Bytes: 8106
Lines: 170

So, it goes without saying, I would not have wanted you to reply to this
draft. I was typing out my reply, then I realized that I hadn't
completely thought out the decider of L_P.

It seems that what made the assertion so self-evident was that I was
assuming the role of a decider and it was obvious to me that I just had
to look at all the cases.

But if I dissociate myself from the decider, I could now ask, 'why does
the decider have to look at everything?' (And my answer is because all
possible outcomes are consistent with everything the decider has been
given a priori).

I realized I couldn't think through this that night, so tried to save my
draft and reply when I had it all, but I somehow sent it anyway.

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

Okay.

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

My reply for this is that I started thinking of M as a skin (or a mask?)
over a Turing machine, so my initial definition of M involves iterating
over sections of the input string and not the strings themselves (same
difference, I suppose).

But another reply is that I actually wanted to provide simpler
definitions. The only feature I really need to preserve is that parts of
strings can be changed to other strings; everything else is degenerate.

But I suspect the reason is that there is no good reason why :) I just
wrote it that way and haven't shown anyone, so no one has said,
"Nnymous, that is a strange way to do things..."

Of course, I'm always open to making things cleaner if they facilitate
communication.


>
> I was talking about the details.  They look clumsy to me.  What you say
> below is straightforward and obvious.
>

Could you explain what you mean by clumsy? To be fair, I'd probably also
need to understand what you meant by 'weak' first.


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

I could always rework this down the line.



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


Again, I rewrote this as I would not have liked to reply this way, but I
shall reply to your replies anyhow

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

>

Okay, noted.

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

I really would have liked to leave this point out at this stage. This is
a technicality stemming from my degenerate definitions. In general, a
recursion need not be built from a TM and need not contain q_accept and
q_reject as symbols.

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


Yup, I should have left this out until we started talking specifics, but
in general R need not be a TM configuration transition function. It's
just a bunch of tuples that have some structure and R(s) is some result
you get if you apply the rules prescribed by R.

Now, we can construct a bunch of these from TMs, so that they have
special properties like whenever a string appears with q_accept, the
outputs of R becomes stationary.

Of course if this recursion was being performed by a TM[*], such a TM
may accept or reject as is necessary, but from the point of view of the
recursion, there is no q_accept or q_reject in the set it recurses over.


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

I mean, I certainly hope not. At the very least, you would have educated
a stranger over the internet on the rudiments of computing theory :)

Also, it's not a different argument. It's more of a change in
perspective.

I had to write one more paragraph (and I suppose we could even subsume
its key ideas into another section) to clarify what deciding a language
would mean in this context, and I had to rewrite another section.

The words are different, but the thinking is the same (when we get to
discussing the text, I would be happy to highlight changes between both
versions).

[*] - Now there's been a subtle (?) shift here which may need me to
re-explain certain things.

Previously, I have been talking about these recursions as another system
of computation assuming that you could use them in place of a TM or
something similar.

But this isn't quite accurate. They actually can't decide things, for
example, so you'd still need something to do the deciding. But I think
the way they have been set up allow them to be useful for other things.