Due:Friday, January 15
Face-to-face students: Submit in class.
Online students: submit a scanned or typed homework by email, as an attachment.
Sipser, exercise 0.2 (a-f), page 25.
Sipser, exercise 0.3 (a-f), page 26.
You can think of a language as a computational problem. You can think of an integer as a string by reprenting it in standard (decimal) notation.
Consider the following language.
S = {n2 | n is a nonnegative integer}That is, S is the set of all perfect squares.
We have defined what it means for a language to be computable. Show that S is computable by describing an algorithm that solves S.