Due. Monday, Jan. 24 at the beginning of class.
Write clearly readable and well thought out answers to all of the following questions.
What is the definition of a language?
What is the definition of a computable language?
Is every finite language computable? Explain.
Is every infinite language uncomputable? Explain.
What is the definition of the halting problem?
A finite state machine can be described by a string in some agreed-upon notation that lists all of the states, says which one is the start state, which ones are yes states, and what the transitions are. If M is a finite state machine, let <M> be a string that describes M in this agreed-upon notation. For simplicity, suppose that the alphabet for the finite state machines is {a,b}.
Let F be the set {<M> | M only answers yes on finitely many different strings.}. That is, <M> is in F just when the set {x in {a,b}* | M answers yes on input x} is a finite set of strings.
Show that F is a computable set by describing how to solve it algorithmically.