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 could suppressor logic be used to solve the Sakamoto 3-SAT problem?) |
||
Line 9: | Line 9: | ||
== How could suppressor logic be used to solve the Sakamoto 3-SAT problem? == | == How could suppressor logic be used to solve the Sakamoto 3-SAT problem? == | ||
− | Definitions | + | '''Definitions''' |
Inputs = framshift suppressor tRNAs | Inputs = framshift suppressor tRNAs | ||
Line 18: | Line 18: | ||
Logical expression (LE) = string of LCs connected by AND | 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. | 1. Individual bacteral cells use Hin/hix system to randomly choose of of the 64 possible combinations of 6 inputs. |
Revision as of 15:12, 4 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.