Theory of Computer Science

The Halting Problem is Noncomputable

• 
  We can prove that (no matter how hard we try) we will never find a program that solves the halting problem (ie: the halting problem is noncomputable)
  
• 
  Assume that we actually have a program H that solves the halting problem.
  

• 
  THE PROOF, by contradiction:
  
  • 
    Show that if H exists then contradictions are provable. Hence H does not exist.
    
• 
  Construct a new program called I that takes as input a program P:
  

I(P) { if (H(P,P)) while (TRUE) ; else return(TRUE); }

• 
  I determines whether P does not halt when given itself as input.
  
• 
  I will go into an infinite loop if P does halt when given itself as input.
  

• 
  Now try to determine the value of I(I) : will I halt when given I as input. There are two cases to consider:
  
  • 
    I(I) returns TRUE and halts
    
    • 
      This means that H says that I does not halt when given I as input  contradiction
      
  • 
    I(I) goes into an infinite loop.
    
    • 
      This means that H says that I halts when given I as input  contradiction
      
  • 
    Conclude that program I cannot exist.
    
• 
  I is constructed from H, so H cannot exist
  
• 
  The halting problem is noncomputable!
  

Other Noncomptable Problems

• 
  The Totality Problem:
  

A program, called T, that solves the Totality Problem takes as input a program P. T outputs TRUE if P would halt when given any possible input, and outputs FALSE otherwise.

If the Totality Problem could be solved, then so could the Halting Problem. the Totality Problem is noncomputable.

• 
  The Equivalence Problem:
  

A program, called E, that solves the Equivalence Problem takes as input two programs P and Q. E outputs TRUE if, given any input, P & Q produce the same output, and E outputs FALSE otherwise.

If the Equivalence Problem could be solved, then so could the Totality Problem. the Equivalence Problem is noncomputable.

• 
  others:
  
  • 
    diophantine equations (impossible to write a program to find the solution for certain polynomial equations over integers)
    
  • 
    basically, any nontrivial property of a program is noncomputable (eg. user input, the order of system calls in an OS, etc...)
    

Time Complexity and Big-O Notation

• 
  Consider this code for adding 7 to each element of an array:
  

for (Index = 0; Index < N; Index++) TheArray[Index] = TheArray[Index] + 7;

How long will it take on a computer?

• 
  The operations performed are:
  
  • 
    Index = 0  once
    
  • 
    Index < N, TheArray[Index] =, + 7, Index++  N times
    
• 
  Time taken is dominated by operations done N times. (ie: is proportional to N  linear)
  
• 
  The proportion depends on the computer time to do <, +, ++
  
• 
  Consider this code for multiplying each element by 2 and adding 7:
  

for (Index = 0; Index < N; Index++) TheArray[Index] = TheArray[Index] * 2 + 7;

How long will it take on a computer?

• 
  The only change is * 2 - N times. The time is taken is still proportional to N.
  
• 
  The Big-O notation says this code is O(N).
  
• 
  This is short hand for saying "proportional to N", and indicates linear complexity.
  
• 
  This is commonly said as "order N".
  

Directory: student
student -> How to Create a Student Recital Program
student -> Tracks, Mixes, Masters, and More!: Analyzing Preservation Priorities for Multitrack Recordings
student -> A chronology 1660-1832 The Restoration Settlement
student -> Introduction
student -> Disaster planning and recovery: post-katrina lessons for mixed media collections
student -> Comparing Hurricanes and Hurricane Seasons
student -> Storm Surge: a rising Danger
student -> Dr. Jeff Masters' WunderBlog
student -> April 9, 2008 Hurricanes (Continued)
student -> Instructions for Writing Hurricane Term Paper

Download 0.58 Mb.

Share with your friends: