CSC103 How Computers Work

Notes 11

Limitations of Computation

1. Alan Turing, 1936
2. The Halting Problem: "given a description of a program [i.e., the source code], decide whether the program finishes running or will run forever. This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever."
3. Infinite loops are a common type of bug (=error).
4. Implication: Impossible to write one program which will definitively "debug" another.

Robotics

1. Roomba
   • iRobot homepage
   • How Roomba works
   • Wikipedia entry
   • 
2. RoboSoccer
   • www.robocup.org
   • RoboCup 2008 Highlights: video (3min)
   • RoboCup 2008 Humanoid League: Goalie Heiner catches ball: video (10sec)
   • 
3. DARPA Grand Challenge
   • Wikipedia entry
     • The course involved a 96 km (60-mile) urban area course, to be completed in less than 6 hours.
     • Rules included obeying all traffic regulations while negotiating with other traffic and obstacles and merging into traffic.
     • The Urban Challenge required designers to build vehicles able to obey all traffic laws while they detect and avoid other robots on the course.
     • this competition operated in a more cluttered urban environment and required the cars to perform sophisticated interactions with each other, such as maintaining precedence at a 4-way stop intersection.
   • DARPA page
   • 2007: NYTimes video emphasizing Stanford's Stanley Jr. (4min)
   • Cornell/MIT crash (1min)
4. Insectoid Robots
   • Boston Dynamics
   • Boston Dynamics Big Dog
   • 

Technological Singularity?

1. Wikipedia on Technological Singularity
2. Recall: Moore's Law
3. Quotes from the Stanford 2007 Singularity Summit: 2007 Quotes
4. Ray Kurzweil @ Singularity Summit (17 min)
5.