Difference between revisions of "Can we solve a 3-SAT problem with supressor logic?"
From GcatWiki
(→What is the 3-SAT problem?) |
(→How could suppressor logic be used to solve the Sakamoto 3-SAT problem?) |
||
| Line 8: | Line 8: | ||
== 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 | ||
| + | |||
| + | 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 | ||
| + | |||
| + | 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. | ||
Revision as of 15:11, 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
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.
