Path: ...!news.misty.com!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: Fri, 27 Sep 2024 09:51:01 +0000
Organization: RetroBBS
Message-ID: <a46dfaa60777b4912ab14bca31e7fef1@www.rocksolidbbs.com>
References: <85955d539da522cf777ab489101c0e2a@www.rocksolidbbs.com> <4b415dd5a91ac648bee8224fc3c28aa19706e06f.camel@gmail.com> <a4cacd3261a32cb9a769fbfe6ed1cd15@www.rocksolidbbs.com> <87cykqgfax.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="3697129"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="/xFkes9bLHN0/d/Gw/bXrNY9v6qZCSvLNzHpjFu4HhU";
User-Agent: Rocksolid Light
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Rslight-Site: $2y$10$xhWNOWZUx1xMN94QHz3OtOE5FHv1nezV//hXUUbyQlx7N1N4JBKI6
X-Rslight-Posting-User: ed1307eaab74f18d8f385bbfbe1f1fa122e0f9be
Bytes: 6464
Lines: 112

On Thu, 26 Sep 2024 23:34:30 +0000, Ben Bacarisse wrote:

> nnymous109@gmail.com (nnymous109) writes:
>
>> Also, I did not know this yesterday, but alternatively, you can access
>> the document directly through the following link:
>> https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
>
> I am hoping that this is a joke.  If it is a joke, then I say well done
> sir (or madam)[*].
>
> But I fear it is not a joke, in which case I have a problem with the
> first line.  If you want two of the states to be symbols (and there are
> points later on that confirm that this is not a typo) then you need to
> explain why early on.  You are free to define what you want, but a paper
> that starts "let 2 < 1" will have the reader wrong-footed from the
> start.
>
> [*] I once went to a contemporary art exhibition where the "catalogue"
> was a set of "theorems" using real mathematical notations but it made no
> sense.  It was fabulous.


Thank you for your reply and for considering the document.

In Mike Terry's words, I'm just using q_accept and q_reject as labels
(i.e., aside from where they are entered into the transition table, they
aren't any different from 0 or 1). The reason I fix them beforehand is
that somewhere in the first construction I make, I want to have the
q_accept and q_reject of every machine be the same symbol.

I made a companion post on Reddit (but my replies are being blocked by
their spam filters), and I was told to give a general idea of what I was
doing, so I provided the following:

-----

My strategy is to define a language over the string representations of
Turing machines. A machine is then admitted into this language if there
is an input for which the machine assumes a certain configuration in the
computation of that input.

The language is in NP because we can give some input as the certificate
of a machine. It is not in P because I'm arguing for some kind of
independence between machine configurations, so that the verifier needs
to spit out all the configurations to assess them.

The verbosity (which I apologize for) comes from my attempts to make
precise these ideas, and to ensure some technicalities (like the
verifier always halting) hold.

-----

The reason I have this scheme of 'recursions' is because I was looking
for a natural way (at least, to me) to observe the configurations of
Turing machines. Say we have the machine's configuration (which doubles
as the input) as:

0 q_a 0 1 0 0 1 ....

where the first element beside the q_a is the current symbol scanned.
Say that symbol and state are updated, and the machine head moves to the
right, the next configuration (and input for the second iteration)
becomes:

0 1 q_b 1 0 0 1 ....

But we can also see this as some substring of the previous configuration
getting replaced with (transformed into) another string. That is, the
substring '0 q_a 0' is replaced with '0 1 q_b'.

Now, q_a is a first-order symbol, so the substring that was transformed
is only three symbols long. A second order symbol, r_b, could transform
substrings seven symbols long, something like: '0 1 q_a r_b 0 1 1' to
'q_f 1 q_j r_c 0 0 1'. Notice that the second order symbols have 'power'
over all symbols with lower order: 1-order symbols (q_*), and 0-order
symbols (0 and 1).

The way I've imagined it: first the zero-order symbols do their thing
(they can only change substrings of length 1 [themselves], so if we want
them fixed, we just have the iteration rules of the 0-order symbols be
empty), then the first-order symbols do their own thing, and so on and
so forth, and we call the resulting process an iteration.

With this scheme, all sorts of things could now be valid inputs, e.g.,
q_accept q_reject 0 1 q_a 0 0 0, so things like standard strings, etc.,
are my way of identifying subsets of inputs that are relevant for the
discussion at hand, e.g., strings like q_0 0 1 1 1 1 where q_0 is what
would ordinarily be an initial state are standard per q_0.

Now, I will bet that this scheme is too general for what we do with it
in the end (all of this is equivalent to some Turing machine, as I note
in 9), so the reason it's this way is two-fold:

First, when I started, I wasn't completely sure where I was headed and
what I would get in the end, and it just felt easier (at least at the
time) to think about it this way (the state is identified with the input
and with the configuration of the machine). Then we get to the end, and,
with the benefit of hindsight, I am pretty sure there is an easier path
to our final conclusion.

The second reason, and why I didn't just do a full re-write, is that I'm
nursing dreams of one day doing work in Statistical Physics/Complex
Systems, and the scheme is reminiscent of that of cellular automata (to
my mind, at least). So, we have nice things (to my mind, again) like the
iterations going on to infinity, except that at some point, the strings
don't change anymore, so there are very very faint ideas of some notion
of equilibrium that I would like to think some more about (probably
using a more general scheme).

But I suppose if you've somehow convinced (deluded?) yourself that
you've said something about P ?= NP, you ought to stop and tell someone
:)