SUNY Geneseo Department of Computer Science

The Halting Problem

Previous Lecture

Misc

SOFI's

Making up the lost tests

• Repeat exam for those who want it ( Thursday, April 22)
• Those who don't want to take it can be graded just on 1st hour exam, final, labs, homework, and readings/mini-assignments, with
  • 1st hour exam worth 25%
  • Final worth 40%
  • Labs worth 20%
  • Rest per syllabus
• After the retest starts, you cannot change your mind about whether or not to take it.

End of semester info

• Final Thursday April 29, 12:00 Noon
  • Comprehensive but biased towards trees and limits of computation
  • Designed for 2 hours, you have 3
  • Open books, notes, computers
  • Same style questions as hour exams
  • Sample Final on Web (see "Exercises" page)
• Labs meet on Monday, April 26

Questions?

Proof for constructor in this week's lab could use strong induction

If you somehow wrote constructor without recursion you can still use induction

The Halting Problem

Chapter 17

Where next?

What does it mean for algorithm to analyze other algorithm/method

• Can represent algorithms as strings

Check for non-terminating programs?

• Sometimes
• Try to create terminate method to tell whether another method stops
• But no such algorithm is possible
  • e.g., barber of Seville
• Because such a program could be used to construct another that did the opposite of what it was supposed to do

Tractable = solution computable in reasonable time

Intractable = not computable in reasonable time

Undecidable = not computable

What is "computable?"

• Doable by a pseudocode algorithm
• This is equivalent to any other definition of "computable"
  • Church-Turing thesis

General solution to halting problem doesn't exist

• Neither (in general) does an "unreachable code" algorithm

Incompleteness of mathematics

• Any usefully expressive notation can state paradoxes

Turing machine = mathematical model of computer

• Defined ca 1936 to answer questions of the form "what can be done algorithmically"
• Not physical machine

Demonstration Program with stub Halting Detector

Moral: computer science has limits, but it can identify those limits

List Review

Questions?

List of lists, want first element of first list

• getFirst returns Object
• getFirst().getFirst() is algorithmically OK
• ((List)getFirst()).getFirst() is OK java
• In some method in subclass
  • ((List)this.getFirst()).getFirst()
• To get first element of head of tail:
  • (from subclass Sub of List that handles getOtherFirst)
  • ((List)((Sub)this.getRest()).getOtherFirst()).getFirst()

Design an algorithm that operates on a list and returns a new list containing the 1st, 3rd, 5th, etc. elements of it

    // In some subclass of List...
    List everyOther()
        if ( this.isEmpty() )
            return this.makeNewList()
        }
        else {
            if ( this.getRest().isEmpty() ) {
                subList = this.makeNewList()
            }
            else {
                subList = this.getRest().getRest().everyOther()
            }
            subList.addItem( this.getFirst() )
            return subList
        }
    }

(No More Lectures Available)