Re: Yet another contribution to the P-NP question

nnymous109@gmail.com (nnymous109) writes:

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.

(1) You could have called them states and no one would have been
startled by the first line of your impenetrable text.

(2) Later, you used as apparent symbols is that Omega U {q_accept,
q_reject} is used to make finite symbol strings.  This is peculiar.

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:

I agree.  Mathematical notation should be used where is help clarify
what you mean.  You seem to use it to obscure what you mean.  You should
be able to explain, in broad terms, how your paper relates to P and NP
using simple language.  At the very least, you need an abstract that
give the broad outline.

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

Pretty much every P=/=NP proof fails because of the assumption about
what a decider needs to do.

I would not bother with any other part of the paper until you can a
certain that you have a proof about what a "verifier needs to do".  Note
that almost everyone wold say that it's obvious that a SAT decider much
check all assignments, but "obvious" is not a proof.  Nothing else
matters but this key step.  All the rest is technical detail.

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.

You need to spell out how it is that this one language has the so far
unique property that it's decider can't be polynomial.

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

"Doubles as" is wrong here.  This input is a string.  The configuration
is a string, a position and a state.  I know you know this (you've
written the state in the middle of a string to show that you know this.

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

Yes.  There are TM-equivalent computational models that simply do string
re-writing.

Now, q_a is a first-order symbol,

It's a state.  But if you also want to treat it as a symbol then you
either need another set of TM's that have their own state sets but that
have symbol sets that include all the q_i of the other kinds of TMs, or
you need to explicitly define a string representation for all the q_i
using only {0, 1}.  I didn't see either being done in the paper, but
then I found it impenetrable.

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

Your words are doing too much work.  Symbols don't transform anything.
And you are not using first and second order in any reasonable way.  At
the very least, define what you mean by "order".  If you just refer me
to your paper, I'll bow out now.

The way I've imagined it: first the zero-order symbols do their thing

How you imagine a symbol "doing it's thing" is useless to me.  To me,
symbols don't "do" anything.  You have to explain what a symbol "doing"
something even means.

(they can only change substrings of length 1 [themselves], so if we
want

Symbols don't change anything either.

I think you are edging your way towards a string re-writing model of
computation, but the words you currently use don't make sense.

I have to stop here, because I have no idea how symbols "do" things, so
you've lost me...

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

--
Ben.