Re: Yet another contribution to the P-NP question

nnymous109@gmail.com (nnymous109) writes:

On Sun, 29 Sep 2024 0:16:42 +0000, Ben Bacarisse wrote:
>

nnymous109@gmail.com (nnymous109) writes:
>

On Fri, 27 Sep 2024 22:42:31 +0000, Ben Bacarisse wrote:
>

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>

On 27/09/2024 00:34, 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.

>
You mean q_accept and q_reject?  It looks like they are just to
represent
the accept and reject states, not tape symbols?  Calling them symbols is
like calling q_0 a symbol, which seems harmless to me - is it just that
you
want to call them "labels" or something other than "symbols"?

>
Later he/she writes
>
   (Omega U {q_accept, q_reject})*
>
where * is, presumably, the Kleene closure.  Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are
used to make "strings" with other tape symbols.
>
I agree that what the states actually are is irrelevant, but that two of
them are later used like this is presumably important.
>

I don't fully get the notation though - e.g. it seems to me that the TMs
have tape symbols and states, but I don't see any state transition
table!

>
Right, but that's line 2 and I was starting at line 1!
>
I thought it might be joke because of the way the author just piles
definition on definition using bizarre notations like integral symbols
but apparently not.

>
Okay, Ben. Please allow me to try again.
>
I'm not completely sure how to use USENET to reply to portions of
replies, so I will try to answer some of your queries here since the
other reply is much longer.

>
I didn't query anything here, did I?  All my significant points were in
mt reply to you.
>

I don't actually use the Turing machines formalism at all in my
arguments until about point 22, so throughout the document I'm not
thinking about Turing machine states and Turing machine symbols and
Turing machine configurations, at all.

>
You don't use it in point 22 either.  You use the words Turing and
machine but you don't use any TM formalism there.
>

But in trying to discuss with others, I tend to just cast the entire
argument in the language of Turing machines, since I felt that that
would be more familiar. Maybe I shouldn't have done that.

>
Your key audience (editors of prestigious journals) will be familiar
with every formalism.  There's nothing to be gained by trying to make
the argument somehow familiar.  Use whatever formalism best explains the
key points.
>

It's probably more accurate to say that I am trying to come up with a
string re-writing model of computation as you pick up on. So everything
is a string, and everything that can be used to form a string is a
symbol, so there's no semantic difference between the following strings:
>
0 0 1 0 0 0 1
>
1 1 q_a r_e 0 0 2 3 d
>
q_accept q_reject q_accept 1 1 q_reject 0 0 0 d f g
>
>
Then we have some rules that tell us to replace substrings of any given
string with another string. That's the entire recursion idea (and yes,
we could do this with a Turing machine, but I'm asking us to forget
about Turing machines momentarily).

>
That's fine.  No reader you care about should have any trouble with your
discussing string re-writing.  They will all have trouble with the
points I made in my reply to you.
>

Also, rather than do a wall of text like last time, I think I should
pause and ask for criticisms here, and then answer them/proceed as is
necessary.

>
Okay, I have noted all that you have said. If there's something worth
preserving in any of the ideas I have, I am perfectly happy to rewrite
these things using more idiomatic expressions.
>
With that introduction out of the way, we're right at the heart of the
thing. Given a string x and a recursion M, if y is the resultant string
upon the action of the recursion, we write M(x) = y.
>
If M(y) = z, then M(M(x)) = z, and equivalently M^2(x) = z.
>
Using S. as the integral symbol*, we let S.(M(x)) be the infinite tuple
<x, M(x), M^2(x), M^3(x), ...>.

Tuples are finite.  S.(M(x)) is an infinite sequence.

More terminology... This is usually referred to as iteration.  The map M
is iterated to generate the sequence s_i = M^i(x).

We call S.(M(x)) the computation of x by M.

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?

If U_M is the set of symbols over which M recurses over,

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.

a property, P,
of M is a subset of U_M.

(you corrected this to U_M*)

S.(M(x)) satisfies P if some substring of some
element of it is in P.

Weird, but OK.  Substring seems to be rather weak, but maybe that's
important later on.

Writing [M] as an appropriate string representation of M and fixing a P,
we can define the set
>
L_P = {[M] such that there exists an x such that S.(M(x)) satisfies P}

OK.

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.

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.

--
Ben.