Chapter I Background







Branches of CS

	- hardware

	- software

	- theory

		- what can be done (aut, comp.)

		- how well can it be done (algorithms)



History

	- parallel postulate

		- Sachieri

		- Riemann

	- Hilbert and axiomatization of mathematics

	- Godel and incompleteness

	- what can be proved, and how?

		- algorithms

			- Church

			- Turing

		- automata

			- McCulloch and Pitts (neurophysiology)

			- Rabin and Scott

		- languages (Chomsky)



Parts of theoretical CS

	- BASIC IDEA is to view the computer as black box    



	1 Formal languages

		- look at how certain input generates certain output

		- Ex 	INPUT: n

			OUTPUT: T if n is even, F if n is odd

			Consider input written as string; z. B., write 3 as aaa. 

			Then input is aaa, output is F. 

		

		The set L = {strings which yield T} is a language.  			

		(In general, any set of strings is a language.)





	2 Automata 

		- draw diagram to represent computation

		- Ex 	same as above.  Represent computation by a "flowchart".



	3 Computability

		- start with simple functions and operations and see how many functions we can generate

		- Ex  Define f as f(n) = n + 1 for all n Î N.  Assume we can compose fuctions.  

			Then we can "generate" the function g(n) = n+2 for all n [is a member of] N.



Problems in theoretical computer science

	- check for correctness

	- check for infinite loops (Halting Problem)



The Halting Problem



	Let A be any program.  Develop an algorithm HP to tell whether or not A halts on every valid input; i.e., 

	A has no infinite loop.



Theorem: The halting problem is unsolvable (i. e., there is no such algorithm HP).



Proof: (by contradiction)  Suppose HP exists.  Then we have the following algorithm:



procedure HP (A);  

begin

    if A has an infinite loop

	then 	writeln ('A does not halt')

	else 	writeln ('A halts')

end;



We could also construct the following procedure:



procedure HP2 (A);  

begin

    if A has an infinite loop

	then 	go into an infinite loop

	else 	writeln ('A halts')

end;





We could also construct a third procedure:



procedure HP3 (A);  

begin

    if A has an infinite loop

	then 	halt

	else 	go into an infinite loop

end;





What result do we get when we call HP3 (HP3)?  

If HP3 has an infinite loop, then HP3 halts, contradiction.

If HP3 does not have an infinite loop, then HP3 goes into an infinite loop, contradiction. Hence, the algorithm HP cannot exist.