0.25
0.5
0.75
1.25
1.5
1.75
2
Computing Exponentially Faster - Implementing a Nondeterministic Universal Turing Machine using DNA
Published on Nov 22, 20161909 Views
The theory of computer science is based around Universal Turing Machines (UTMs): abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of UTMs.
Related categories
Chapter list
Computing Exponentially Faster: Implementing a Universal Nondeterministic Turing Machine Using DNA00:00
Universal Turing Machines (UTMs)00:32
Universal Turing Machines 01:56
UTMs: Maths or Physics?02:39
Complexity Theory - 105:17
Complexity Theory - 206:35
The Feasibility Thesis06:51
Complexity Classes07:18
NP Problems07:33
P ≠ NP ? - 108:29
P ≠ NP ? - 210:04
Maths v Physics (again)11:49
Nondeterministic UTMs (NUTMs)13:30
The Ontology of NUTMs14:30
Accepting-state16:39
Thue Systems - 116:58
Thue Systems - 217:55
A Universal Thue System18:46
State Transition: ca →ac19:44
Start-state20:24
Molecular Biology21:09
DNA21:31
Polymerase Chain Reaction (PCR)22:31
PCR24:14
Site Directed Mutagenesis26:16
DNA Computing - 127:18
DNA Computing - 227:51
Adelman’s Model29:37
Building a NUTM using DNA31:02
Design of a NUTM31:07
Symbols32:11
Encoding of Symbols - 132:15
Encoding of Symbols - 232:37
Symbols Used34:37
Writing Programs35:15
The Accepting State35:47
Computer Architecture36:43
Mix36:53
Application of a Rule to all States37:22
Rule Implementation37:24
Recognition - 138:04
Recognition - 238:42
The Boltzmann Distribution39:15
Recognition - 340:23
Simulation40:45
Execution41:14
Microprogramming - 141:18
Microprogramming - 241:52
Changing a Symbol41:59
Recognition - 442:06
Change – strand 142:10
Removing the Clamp42:21
Change – strand 242:26
Example Symbol Manipulation42:37
Symbol Interchange42:50
Status of the Design43:01
Noise - 143:40
Noise - 244:32
Limitations of NUTMs45:07
Synthetic Biology46:22
Co-NP Machine47:35
PSPACE Machine?48:40
PSPACE 49:27
PSPACE v Physics49:41
Quantum Computing50:57
Is the Universe a NUTM?53:08
Conclusions54:57
Acknowledgments55:30