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: Sun, 29 Sep 2024 15:19:32 +0000 Organization: RetroBBS Message-ID: <3f36b24ff7a1d155688df8517ffc4032@www.rocksolidbbs.com> References: <85955d539da522cf777ab489101c0e2a@www.rocksolidbbs.com> <4b415dd5a91ac648bee8224fc3c28aa19706e06f.camel@gmail.com> <87cykqgfax.fsf@bsb.me.uk> <877cawhg6g.fsf@bsb.me.uk> <793e0d649cf836d3b0bbdf9c1f946091@www.rocksolidbbs.com> <87v7yffh5h.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="4019257"; mail-complaints-to="usenet@i2pn2.org"; posting-account="rrhMWBcDAx1rC5+om1CWMH+W6SvwsR4AkzPL9w80GDY"; User-Agent: Rocksolid Light X-Rslight-Site: $2y$10$kLoC3H7H2LfIplaDLPJFEOY2.SdWI0AqWRAkS3XSH4oJ7zdcsde0K X-Spam-Checker-Version: SpamAssassin 4.0.0 X-Rslight-Posting-User: 997a80a59f36bca0d6daf54c90c3284ff767f4d5 Bytes: 7836 Lines: 147 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 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 . We call S.(M(x)) the computation of x by M. If U_M is the set of symbols over which M recurses over, a property, P, of M is a subset of U_M. S.(M(x)) satisfies P if some substring of some element of it is in P. 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} 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. 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. * - 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. ** - 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. *** - 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.