1David Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceClass 33:Computing with Photons and LifeFrom The Tinkertoy Computer and Other Machinationsby A. K. Dewdneyhttp://www.amazon.com/exec/obidos/tg/detail/-/071672491X/103-4408705-5367831?v=glance2CS150 Fall 2005: Lecture 33: Alternate Computing ModelsChurch-Turing Thesis• Church’s original (1935)– Lambda calculus is equivalent to real world computers (can compute any computable function)• Turing’s version – “Every function which would naturally be regarded as computable can be computed by a Turing machine.”• Generalized version:– Any computation that can be done by an algorithm can be done by a mechanical computer– All “normal” computers are equivalent in computing power3CS150 Fall 2005: Lecture 33: Alternate Computing ModelsTuring Machines and Complexity• Stronger version:– Complexity classes P, NP, and NP-complete are defined for Turing machine steps, but apply identically to all “normal” computers• Today: “Abnormal” Computers–Mightchange what is computable (probably don’t)– Do change what a normal “step” is4CS150 Fall 2005: Lecture 33: Alternate Computing ModelsNormal Steps• Turing machine:– Read one square on tape, follow one FSM transition rule, write one square on tape, move tape head one square• Lambda calculus:– One beta reduction• Your PC:– Execute one instruction (?)• What one instruction does varies5CS150 Fall 2005: Lecture 33: Alternate Computing ModelsGeneralized Normal Steps• Require a constant amount of time• Perform a fixed amount of work– Localized– Cannot scale (indefinitely) with input size6CS150 Fall 2005: Lecture 33: Alternate Computing ModelsAbnormal Imaginary Computer• “Accelerating” TM– Like a regular TM, except the first step takes 1 second, second step takes ½ second, third step takes ¼ second, ... nthstep takes 1/2nsecond• Is our “Accelerating” TM more powerful than a regular TM?27CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQuantum Physics for Dummies• Light behaves like both a wave and a particle at the same time• A single photon is in many states at once• Can’t observe its state without forcing it into one state• Schrödinger’s Cat– Put a live cat in a box with cyanide vial that opens depending on quantum state– Cat is both dead and alive at the same time until you open the box8CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQuantum Computing• Feynman, 1982• Quantum particles are in all possible states• Can try lots of possible computations at once with the same particles• In theory, can test all possible factorizations/keys/paths/etc. and get the right one!• In practice, very hard to keep states entangled: once disturbed, must be in just one possible state 9CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQubit• Regular bit: either a 0 or a 1• Quantum bit: 0, 1 or in between– p% probability it is a 1• A single qubit is in 2 possible states at once• If you have 7 bits, you can represent any one of 27different states• If you have 7 qubits, you have 27different states (at once!)10CS150 Fall 2005: Lecture 33: Alternate Computing ModelsQuantum Computers Today• Several quantum algorithms– Shor’s algorithm: factoring using a quantum computer• Actual quantum computers– 5-qubit computer built by IBM (2001)– Implemented Shor’s algorithm to factor:• “World’s most complex quantum computation”– Los Alamos has built a 7-qubit computer• To exceed practical normal computing need > 30 qubits– Adding another qubit is more than twice as hard15 (= 5 * 3)11CS150 Fall 2005: Lecture 33: Alternate Computing ModelsComplexity for Quantum Computer• Complexity classes are different than for regular computers, because a step is different• Quantum computer: each step can take both possible decisions at once– Means a quantum computer is a nondeterministic computer!– It can solve problems in class NP in polynomial time!• What matters?Number of qubits you needNumber of (nondeterministic) steps12CS150 Fall 2005: Lecture 33: Alternate Computing ModelsComputing with DNALeonard Adleman(Mathematical Consultant for Sneakers), 1995313CS150 Fall 2005: Lecture 33: Alternate Computing ModelsDNA• Sequence of nucleotides: adenine (A), guanine (G), cytosine (C), and thymine (T)• Two strands, A must attach to T and G must attach to CAGTCC14CS150 Fall 2005: Lecture 33: Alternate Computing ModelsHamiltonian Path Problem• Input: a graph, start vertex and end vertex• Output: either a path from start to end that touches each vertex in the graph exactly once, or false indicating no such path existsCHORICIADBWIstart: CHOend: BWIHow hard is the Hamiltonian pathproblem?15CS150 Fall 2005: Lecture 33: Alternate Computing ModelsEncoding The Graph• Make up a two random 4-nucleotide sequences for each city:CHO: CHO1= ACTT CHO2= gcagRIC: RIC1 = TCGG RIC2 = actgIAD: IAD1 = GGCT IAD2 = atgtBWI: BWI1 = GATC BWI2 = tcca• If there is a link between two cities (A→B), create a nucleotide sequence: A2B1CHO→RIC gcagTCGGRIC→CHO actgACTTBased on Fred Hapgood’s notes on Adelman’s talkhttp://www.mitre.org/research/nanotech/hapgood_on_dna.html16CS150 Fall 2005: Lecture 33: Alternate Computing ModelsEncoding The Problem• Each city nucleotide sequence binds with its complement (A ↔ T, G ↔ C) :CHO: CHO1= ACTT CHO2= gcagCHO’: TGAA cgtcRIC: TCGGactgRIC’: AGCCtgacIAD: GGCTatgt IAD’ = CCGAtacaBWI: GATCtcca BWI’ = CTAGaggt• Mix up all the link and complement DNA strands – they will bind to show a path!17CS150 Fall 2005: Lecture 33: Alternate Computing ModelsPath BindingCHORICIADBWIACTTgcagTCGGactgGATCtccaGGCTatgtCHO’TGAAcgtcgcagGGCTCHO→IADIAD’CCGAtacaatgtTCGGIAD→RICRIC’AGCCtgacBWI’CTAGaggtactgGATCRIC→BWI18CS150 Fall 2005: Lecture 33: Alternate Computing ModelsGetting the Solution• Extract DNA strands starting with CHO and ending with BWI – Easy way is to remove all strands that do not start with CHO, and then remove all strands that do not end with BWI• Measure remaining strands to find ones with the right weight (7 * 8 nucleotides)• Read the sequence from one of these strands419CS150 Fall 2005: Lecture 33: Alternate Computing ModelsWhy don’t we use DNA computers?• Speed: shaking up the DNA strands does 1014operations per second ($400M supercomputer does 1010) • Memory: