DOC PREVIEW
Rutgers University CS 105 - How Universal Are Turing Machines?

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 4:How Universal Are Turing Machines?CS105: Great Insights in Computer SciencePhilosophy• Some fields are ignored by philosophers (civil engineering, primatology).• Computer Science is not so lucky.- What does it mean to “know” something?- What is “intelligence”?- Do objects “compute” their movements?Great Humiliations?• Freud: - Astronomy (Galileo): Our world is just another world.- Natural History (Darwin): Our species is just another species.- Psychoanalysis (Freud): Consciousness is just another mental process.• Hillis: - Computer Science (Turing?): Our mind is just another computing device.What Can’t Computers Do?• To fight this idea, philosophers are fond of finding things that computers can’t do.- No one gets wet from a computer simulation of a hurricane (Dennett).- Translate human languages (Dreyfus).- Be self reflective or conscious (Lucas).Kinds of ComputationChurch’s lambda calculus:mathematical functionnotationTuring machine:finite-state machine +memory tapeVon Neumann architecture:finite-state machine +memory tapeChomsky’s context-sensitive grammars:string rewrite rulesPost Correspondence:string extension rulesprogramming languages:instructions, loops, subroutinescan simulateJonesing for MarioNestopiaiEmulatorChurch-Turing Thesis• Usually taken to mean that any machine computation can be carried out on a Turing machine.• Sometimes expanded to mean that any physical system can be simulated on a Turing machine. • And, since brains are physical systems, our minds must be equivalent to Turing machines!The Element of Surprise• A lot of CS research has gone into understanding the powers, limits, and philosophy of... coin flips!• Later, I’ll show how computers use a bit of randomness to speed up their computations.• For now, let’s take a brief sidebar into some probability theory that will be useful.Using Random Bits• Since numbers are made of bits, we can generate a random number using random bits.• If there’s a way to create random bits (coin flips), how make a random number from 0 to 3 (dreidel)?• How about 0 to 15?• Tricky: How about 0 to 2?Examplesdef rand4(): return randbit()* 2 + randbit()def rand16(): return randbit()* 8 + randbit()*4 + randbit()* 2 + randbit()def rand3(): x = 3 while x == 3: x = randbit()* 2 + randbit() return x(1 1/3 calls per random number. 0, 1, 2 equally likely.)State of the Art• The ... Mersenne twister algorithm, by Makoto Matsumoto and Takuji Nishimura in 1997 ... has a colossal period of 219937-1 iterations (probably more than the number of computations which can be performed in the future existence of the universe), is proven to be equidistributed in 623 dimensions (for 32-bit values), and runs faster than all but the least statistically desirable generators.• Python has a package for this generator.Demo: Guess My Bit• Six rounds:- Guess my bit. If wrong, you’re out.- Can anyone survive all 6 rounds?Probability Theory• If event has probability p, 1/p tries before it happens (on average).• If n distinct events are equally likely, ~n ln n tries before we see all n of them (order independent) or n2 (in order).• If we start with a number n, we can cut it in half log n times before 1 is reached.How About This?• Start with a number n.• Change it to a number between 1 and n at random.• Stop when you reach 1.• How many times do we do the change before 1 is reached (on average)?I Don’t Know• Here’s a different game, which has to take no less time than the one I just described.• With probability 1/2, don’t change n. With probability 1/2, change n to n/2.• On average, 2 tries before n is halved and log n halves before 1 is reached.• So, like 2 log n.Quantum Effects• Pseudo-random-based encryption always has a chance of being cracked.• Only source of true randomness: quantum mechanics (the rest of physics is deterministic, if chaotic).• Einstein didn’t like it. Tough.Quantom RandomnessQuantum Computer• A quantum bit (qubit) is simultaneously zero and one (a superposition). n qubits can represent 2n possibilities.• When you look, one possibility presents itself, according to well understood probabilistic rules. A kind of parallel search.• Shor: A computer with qubits can factor numbers in polynomial time!If Factoring is Easy...• quantum computers invalidate standard cryptosystems. No more secrets.• However, they also open up some wild possibilities.• quantum cryptography: qubits can be completely random and correlated at a distance. Can be used to send completely secret messages.Today’s Advice• My only piece of advice for today:• Don’t listen to anything I say today; it will hurt your head.Self Contradiction• The main topic today is self reference and self contradiction.• The idea is that “interesting” things happen when something can refer to itself and assert that it has properties that negate its own existence.Oxymorons• We’re all familiar with oxymorons: words that harbor two conflicting meanings.• Top ten list from http://www.oxymoronlist.com/:20. Government Organization19. Alone Together18. Personal Computer 17. Silent Scream16. Living Dead15. Same Difference14. Taped Live13. Plastic Glasses12. Tight Slacks11. Peace Force10. Pretty Ugly9. Head Butt8. Working Vacation7. Tax Return6. Virtual Reality5. Dodge Ram4. Work Party3. Jumbo Shrimp2. Healthy Tan1. Microsoft WorksSurface Contradiction• Examples seem incongruous, but they all actually make sense.- “jumbo shrimp” just means pretty big for a shrimp, which makes perfect sense. Like “pretty fly for a white guy”.• The contradiction isn’t very deep.You Don’t Say...• I always say, "Silence is golden."• We're not f-ing bitter!• I remain silent.• I am not in denial.• Eschew obfuscation.• When you least expect it, expect it.• But, I don't speak English.• I’m not talking to you.• I can’t talk right now.• I’m sorry, but I just don’t care.• Leave me be, I’m asleep.• I’m speechless.• I prefer not to have an opinion.Unquotable• Know what I hate most? Rhetorical questions. (Camp)• They all laughed when I said I was going to be a comedian. Well, they're not laughing now. (Munkhouse)• If there is anything the nonconformist hates worse than a conformist, it's another nonconformist who doesn't conform to the prevailing standard of


View Full Document

Rutgers University CS 105 - How Universal Are Turing Machines?

Download How Universal Are Turing Machines?
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view How Universal Are Turing Machines? and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view How Universal Are Turing Machines? 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?