Deutsch English Français Italiano |
<00b5dad9473a86e602c8e4573322e814@www.rocksolidbbs.com> View for Bookmarking (what is this?) Look up another Usenet article |
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: Mon, 30 Sep 2024 01:53:25 +0000 Organization: RetroBBS Message-ID: <00b5dad9473a86e602c8e4573322e814@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> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: i2pn2.org; logging-data="4083311"; mail-complaints-to="usenet@i2pn2.org"; posting-account="rrhMWBcDAx1rC5+om1CWMH+W6SvwsR4AkzPL9w80GDY"; User-Agent: Rocksolid Light X-Rslight-Posting-User: 997a80a59f36bca0d6daf54c90c3284ff767f4d5 X-Rslight-Site: $2y$10$nghlN5PxXvQOzS0Kct7mRuvUrqaCxmou2MT9bvC2uQq1d6/eqsAOi X-Spam-Checker-Version: SpamAssassin 4.0.0 Bytes: 6856 Lines: 140 On Sun, 29 Sep 2024 23:19:02 +0000, Ben Bacarisse wrote: > Tuples are finite. S.(M(x)) is an infinite sequence. Ok, noted. Is it that it is a tuple whenever it is finite, but when that constrained is relaxed and it is allowed to be a infinite, it is more appropriate to call it a sequence? > > More terminology... This is usually referred to as iteration. The map M > is iterated to generate the sequence s_i = M^i(x). I see. I shall use iterations instead. > 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? > Yes, provided you're interpreting something like 'q_0 1 1 1 0' that I would a call a string as just a TM configuration. > 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. > Okay, would 'iterates over' be better? What I'm trying to get is say we have some string G = 0 q z 1 0 1 and z is not in U_M, M can still act on G in the following manner: if M contains a rule that '0 q e' should be transformed into '1 1 q_b' where e is the empty string, M(G) = 1 1 q_b z 1 0 1 > Weird, but OK. Substring seems to be rather weak, but maybe that's > important later on. > It allows us to extend things like halting. Say I build M using the transition table of a Turing machine and at some point in the computation, M^i(x) is 0 1 q_accept 1 1. Because we built M from a TM, it will be the case that M^(i+1)(x) = M^i(x) 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. >> 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. > Okay, if I may re-render your guess using my terminology, we would have s in S iff S.(R(s)) satisfies P1 = {q_accept} s not in S iff S.(R(s)) satisfies P2 = {q_reject} which is almost correct except for three points 1) We need to specify that the property satisfaction takes place after the computation has become stationary. 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*. 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 [*] So, to decide L_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. >> >> ** - 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.