Difference between revisions of "Can we solve a 3-SAT problem with supressor logic?"
From GcatWiki
(→How could suppressor logic be used to solve the Sakamoto 3-SAT problem?) |
(→How did Sakamoto et al. use a DNA computer to solve a 3-SAT problem?) |
||
| Line 4: | Line 4: | ||
[http://gcat.davidson.edu/GcatWiki/images/3/39/Sakamoto_DNA_computer_3SAT.pdf Sakamoto et al.] | [http://gcat.davidson.edu/GcatWiki/images/3/39/Sakamoto_DNA_computer_3SAT.pdf Sakamoto et al.] | ||
| + | |||
| + | |||
| + | <center> [[Image:hairpin.GIF]]<br></center> | ||
== What is suppressor logic? == | == What is suppressor logic? == | ||
Revision as of 19:55, 7 April 2009
Contents
What is the 3-SAT problem?
How did Sakamoto et al. use a DNA computer to solve a 3-SAT problem?
What is suppressor logic?
How could suppressor logic be used to solve the Sakamoto 3-SAT problem?
Definitions
Inputs = framshift suppressor tRNAs
Input value = supp a is 1, supp g is 0; supp b is 1, supp h is 0, etc. up to tth 6th pair of f and l
Logical clause (LC) = three inputs connected by OR, eg. (a OR b OR e)
Logical expression (LE) = string of LCs connected by AND
Subroutine
1. Individual bacteral cells use Hin/hix system to randomly choose of of the 64 possible combinations of 6 inputs.
2. Each bacterial cell carries out the following subroutine on each LC: IF LC=TRUE THEN "check the next LC" ELSEIF LC=FALSE "go get a new set of inputs with step 1"
3. If/when a bacterial cell finds a set of inputs that satisfies the entire LE (ie. a solution to the 3-SAT problem), it will glow green.
