RNA-computing CAs feasibility

For discussion directly related to ConwayLife.com, such as requesting changes to how the forums or home page function.
Post Reply
Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

RNA-computing CAs feasibility

Post by Koiti Kimura » May 3rd, 2018, 4:34 am

Are any such things feasible?
And are messenger-RNAs imitations by CAs possible? Was the RNA-computing by L. F. Landweber et al a messenger-RNAs-imitation?
(Cukras, A.R., Faulhammer, D., Lipton, R.J. and Landweber, L.F.: Chess games: a model for RNA based computation, "BioSystems," Vol.52, pp.35-45, 1999.)

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: RNA-computing CAs feasibility

Post by dvgrn » May 3rd, 2018, 10:34 am

Koiti Kimura wrote:Was the RNA-computing by L. F. Landweber et al a messenger-RNAs-imitation?
I haven't read the paper, but it seems unlikely to be an "imitation" given that it used actual RNA. This question seems just about as vague as your previous question of a few days ago -- did you really need another new thread for this one?
Abstract of Landweber paper: Here we develop the theory of RNA computing and a method for solving the 'knight problem' as an instance of a satisfiability (SAT) problem. Using only biological molecules and enzymes as tools, we developed an algorithm for solving the knight problem (3 x 3 chess board) using a 10-bit combinatorial pool and sequential RNase H digestions. The results of preliminary experiments presented here reveal that the protocol recovers far more correct solutions than expected at random, but the persistence of errors still presents the greatest challenge.
From an article in the-scientist.com:
Her RNA computer was hailed at the time as the world champion by computer scientist Leonard Adleman of the University of Southern California. But Landweber subsequently chose to move on to other projects. "DNA computing is a difficult field to work in," she explains. "Silicon computers have had a 50-year head start, so the bar is set so high for a computation to be a meaningful one that it makes the field of wet computers pretty daunting. We didn't see the killer application, and most people in that field have shifted their interest toward building DNA molecules rather than using DNA molecules to solve problems faster than a computer can."
DNA/RNA-based computing does potentially have some commonality with CAs. It's possible to operate on a large area or a large number of potential solutions all at once.

It seems as if it should be possible to design a CA that starts with a random field and stabilizes into a valid solution to "the knight's problem". -- There are at least three different optimization puzzles that have been called "the knight's problem", by the way, but in this case the problem seems to be to put the largest number of knights on an MxN chessboard such that no knight threatens any other knight.

It's hard to see how either RNA or CAs can really make an exciting contribution to this problem, because of the difficulty of designing a system that's guaranteed to come out with an optimal solution instead of just a valid one. In either case you could make a column of candidate solutions in descending order of population, and test them with a CA rule or a physical RNA-based system. The first candidate that doesn't change is an optimal solution.

But that requires pre-constructing all candidates. That's easy enough for 3x3, but the task gets exponentially harder as the size increases. So this is certainly not a practical way of finding that optimal solution.

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: RNA-computing CAs feasibility

Post by Koiti Kimura » May 3rd, 2018, 10:50 pm

So, is DNA/RNA-based computing just/merely a kind of probabilistic (guesswork or approximation) computation? But don't the actual DNA and RNAs work on a proper/right non-guesswork/approximation basis/principle for the one valid solution instead of some optimal solution(s)? I mean, aren''t any CAs-imitations of such a proper principle feasible?

By the way, believe it or not, I have these P=NP proofs using dmd (diagonal method disproofs) etc. and this 3-coloring problem solution utilizing 4-Coloring Theorem. If they should be valid/true, would the answer to the last question in my previous paragraph be "yes"?

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: RNA-computing CAs feasibility

Post by 77topaz » May 4th, 2018, 2:47 am

Koiti Kimura wrote:By the way, believe it or not, I have these P=NP proofs using dmd (diagonal method disproofs) etc. and this 3-coloring problem solution utilizing 4-Coloring Theorem. If they should be valid/true, would the answer to the last question in my previous paragraph be "yes"?
That's a bit of an outlandish claim, as the P vs. NP problem is one of the most famous and long-standing unsolved problem in mathematics, and the four-colour theorem required a large amount of computing power to prove. So, I think you're not expressing yourself/explaining correctly what you mean.

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: RNA-computing CAs feasibility

Post by Koiti Kimura » May 4th, 2018, 3:56 am

I understand very well as common-sensical your opinion about my claim.

But believe me: e. g. , dmd's are so simple/foolproof:

A. 2 < Aleph0, so Aleph1 = 2^Aleph0 ≦ (is equal to or smaller than) Aleph0^Aleph0 = Aleph0 (all by the proofs by Cantor himself);

B. iff Goedel logical formula is G, then G = not-provable (G), then not G = provable (G) = G, and it is contradictory, so the diagonal lemma in Goedel's "Proof" must be wrong.

As you know, all the existent P ≠ (not equal) NP "proofs" use dm's: Fortnow's, Sipser's, etc.
And I also have non-reductio-ad-absurdum/counter-proof, positive/offensive/aggressive/active/non-passive P = NP proofs.


As for 3-coloring, you simply have to trust me, judging from the above dmd's. I fail to know how to upload the graph for the proof.
Last edited by Koiti Kimura on May 4th, 2018, 9:35 pm, edited 1 time in total.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: RNA-computing CAs feasibility

Post by Majestas32 » May 4th, 2018, 8:49 am

Koiti Kimura wrote:
As for 3-coloring, you simply have to trust me, judging from the above dmd's. I fail to know how to upload the graph for the proof.

Sounds like fermat :D
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: RNA-computing CAs feasibility

Post by blah » May 7th, 2018, 2:51 pm

I have a proof that 1=2, but these forums don't let you make a post big enough to contain it. I have also proven that 2 does not equal 1, and therefore equality is not commutative. You'll just have to take my word for it, trust me, I'm a genius.
succ

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: RNA-computing CAs feasibility

Post by gameoflifemaniac » May 8th, 2018, 9:07 am

blah wrote:I have a proof that 1=2, but these forums don't let you make a post big enough to contain it. I have also proven that 2 does not equal 1, and therefore equality is not commutative. You'll just have to take my word for it, trust me, I'm a genius.
But please try to post attachments with the proofs!
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: RNA-computing CAs feasibility

Post by toroidalet » May 8th, 2018, 11:03 am

gameoflifemaniac wrote:
blah wrote:I have a proof that 1=2, but these forums don't let you make a post big enough to contain it. I have also proven that 2 does not equal 1, and therefore equality is not commutative. You'll just have to take my word for it, trust me, I'm a genius.
But please try to post attachments with the proofs!
the problem here, of course, is that the proof requires advanced theorems in the disparate fields of quantum sociology and a conjecture based on Graham's number, and that's just the simplest theorems required. This proof is in an area of mathemology so advanced that no one else has dared to enter it. The proof can't even be uploaded to dropbox or google drive or something; it has trillions of cases identified in its transinfinite induction, not to mention hundreds-of-pages-long proofs for each involving multiple horrendous quadruple sums. You would probably find the proof completely intractable if you were to read it, so don't even bother, as you likely will get a headache and probably need sleep, as you can't just read it in a year.
And that's just the abstract.
Interestingly, it does prove that Fermat's Last Theorem is false.


(it was supposed to be a joke, blah hasn't actually proven that 1=2. Don't believe everything you hear on the internet, kids.)
Any sufficiently advanced software is indistinguishable from malice.

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: RNA-computing CAs feasibility

Post by gameoflifemaniac » May 9th, 2018, 12:53 pm

toroidalet wrote:
gameoflifemaniac wrote:
blah wrote:I have a proof that 1=2, but these forums don't let you make a post big enough to contain it. I have also proven that 2 does not equal 1, and therefore equality is not commutative. You'll just have to take my word for it, trust me, I'm a genius.
But please try to post attachments with the proofs!
the problem here, of course, is that the proof requires advanced theorems in the disparate fields of quantum sociology and a conjecture based on Graham's number, and that's just the simplest theorems required. This proof is in an area of mathemology so advanced that no one else has dared to enter it. The proof can't even be uploaded to dropbox or google drive or something; it has trillions of cases identified in its transinfinite induction, not to mention hundreds-of-pages-long proofs for each involving multiple horrendous quadruple sums. You would probably find the proof completely intractable if you were to read it, so don't even bother, as you likely will get a headache and probably need sleep, as you can't just read it in a year.
And that's just the abstract.
Interestingly, it does prove that Fermat's Last Theorem is false.


(it was supposed to be a joke, blah hasn't actually proven that 1=2. Don't believe everything you hear on the internet, kids.)
I'm dumb
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: RNA-computing CAs feasibility

Post by Koiti Kimura » May 9th, 2018, 9:44 pm

1. Sorry: my 3-Coloring Theorem "proof" has proved to be wrong/false after more careful considerations.
2. But I'm sure you see that my Cantor/Goedel-DMd's (Doctorate of Math disqualifications) are absolutely fool-proof truths; so, the P=NP proofs that are based on the DMd's or not based on them still live.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: RNA-computing CAs feasibility

Post by 77topaz » May 9th, 2018, 10:21 pm

Koiti Kimura wrote:(Doctorate of Math disqualifications)
Okay, now I'm convinced you're just trolling us.

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: RNA-computing CAs feasibility

Post by Koiti Kimura » May 10th, 2018, 12:50 am

NO! I am seriously "eager" (so to speak) for the progress of the math including future CA theories and DNA/RNA computing theories, believe me. If you feel disgusted at my sounding arrogant or provocative, excuse me. But I am a believer in Good Samaritanism, honest! I was wondering if I might be of any help to this field/discipline of math, namely, if I could give the slightest hint for any progress in it, even with the scarcest knowledge of mine. At least, trust in my lack of any malice.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: RNA-computing CAs feasibility

Post by dvgrn » May 10th, 2018, 9:58 am

Koiti Kimura wrote:I was wondering if I might be of any help to this field/discipline of math, namely, if I could give the slightest hint for any progress in it, even with the scarcest knowledge of mine.
As far as proving P-vs.-NP, there are some good (and entertaining) resources out there describing experts in the field who have gotten buried by floods of purported proofs and disproofs by non-experts, and who eventually have to throw in the towel and declare that they're simply not going to look at any more of them -- at least unless they're interestingly different from all the others!

Here's a good list of attempted contributions to the field that got as far as a completed paper (though not a peer-reviewed paper, with one single exception out of more than a hundred).

That link also notes that there's a million-dollar Clay Mathematics Institute prize attached to the P-vs.-NP question. So 1) if you have a solution, this thread isn't the place for it, and 2) don't expect it to be easy to get past the wall of understandable doubt on the part of any reasonable person reading claims of this kind.

I think this is the statement from an "exhausted P-vs.-NP expert" that I remember from years ago:
Oded Goldreich wrote:In my FAQ page, I stated that I will refuse to check claims regarding the resolution of famous open problems such as P versus NP. I would also advi[s]e other experts to do the same, unless the claim is augmented by a clear and convincing indication as to how this work succeeds where many others have failed.

Needless to say, the famous open problems of Computer Science are very appealing, interesting, and natural. As such, they also attract the attention of non-experts, and one annoying consequence is a flood of false claims of resolutions of these problems. These claims are never supported by any new insight nor a clear and convincing argument as to what makes the authors believe that they have succeeded where many others have failed. Having the relatively few expert proofread all these false claims would constitute a vast waste of scarce resources.

It is indeed possible that a non-expert may succeed where experts have failed, but such an event is very unlikely. Furthermore, I believe that in such a case, the successful non-expert will be able to convince the scientific community that his/her claim is indeed valid, and in particular will be able to bypass or break the ``wall of refusal'' erected in the previous paragraph. In particular, it is most likely, that he/she will be able to present a novel insight that would be intriguing enough to convince experts to read the work.

I do not advocate not thinking about the famous open problems, although in my opinion a fruitful approach would be to try to gain more understanding (via easier related problems) rather than trying to make a super-ultra-giant step.
Back to the intended topic of the thread:
Koiti Kimura wrote:So, is DNA/RNA-based computing just/merely a kind of probabilistic (guesswork or approximation) computation? But don't the actual DNA and RNAs work on a proper/right non-guesswork/approximation basis/principle for the one valid solution instead of some optimal solution(s)? I mean, aren''t any CAs-imitations of such a proper principle feasible?
This still seems too vague to be answerable. If you try to build a CA that's somehow equivalent to the RNA method of solving the "knight's problem", for example, you'll very likely find that that it's not in the least reasonable to model RNA matching with the required "10-bit combinatorial pool" inside a CA -- it would need too many states, or too much complex structure, ultimately for no useful purpose.

What you would really do is throw away the whole RNA-computing idea and solve the knight problem in some reasonable CA-based way -- maybe somewhat analogous to what calcyman did in early versions of apgsearch with special rule tables for removing blinkers and blocks. For example, you might end up with a custom rule that is stable in the presence of a valid solution to the knight problem but unstable otherwise.

Unfortunately that doesn't guarantee a provably optimal solution, so you'd probably have to do a lot more work on the specifics to come up with anything really new or interesting.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: RNA-computing CAs feasibility

Post by Macbi » May 10th, 2018, 2:02 pm

Also, if you have a proof of P != NP, then publish it. But if you prove P=NP and create an efficient algorithm for solving NP problems then you have a bit more of a problem.

If you publish the algorithm then everyone's cryptography suddenly stops working at once and you destroy the entire financial system. So you should give some warning before you release the algorithm. But if you let people know who you are then the CIA (or similar) will kidnap you and torture you until you give them the algorithm. So the correct thing to do is to announce your solution anonymously. You can prove that your algorithm works by publishing the solution some pre-existing well-publicised hard NP-complete problem. Then once people have had some time to understand what's going on you can release the algorithm.

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: RNA-computing CAs feasibility

Post by Koiti Kimura » May 11th, 2018, 12:13 am

1. I fail to have got any actual concrete NP problems solution algorithms yet. What I HAVE managed to do is prove that they can be solved within the P problems solution time periods in principles, or (in other words), basically somehow (with some unknown methods), and the proofs employed the dmd's or other tools.

2. I would like to give my heartfelt apology to dm supporters because I as a Christian must never look down on them; I take back the jeering remark containing the "Doctorate of Math disqualifications"; I did not mean it; I jotted it down, carried away by Satan's temptation. If it hurt anyone's feelings, excuse me; actually, I willingly admit that Cantor, Goedel and other dm misusers were/are real geniuses and have left great legacies behind: e.g., Cantor, his transfinite arithmetic; Goedel, his Completeness Theorem, which had to be supplemented with Incompleteness/Inconsistency "Theorem" disproofs: those feats of theirs were indispensible for the "God-as-the-only-Infinity (Infinite-Resources-Possessor)-and-unique/single-Omniscient" Christian-theology revealed to me.

Post Reply