Some Questions and Answers about EXAM in UIT2201
================================================

A student emailed me some questions (last minute) and I felt
that my answer may also be useful to all, so they are posted here.
Name have been replaced by "... a student ..." because I have
not asked for permission to post the name.
More will be posted if relevant.

--hon-wai (Sunday 27-April)


-------------------------------------------------------------
|>-  -----Original Message-----
|>-  From: ... a student ...
|>-  Sent: Sunday, April 27, 2003 2:10 AM
|>-  To: leonghw@comp.nus.edu.sg
|>-  Subject: Some queries
|>-  
|>-  Dear Prof. Leong,
|>-   
|>-  I know this is a bit last minute but I have a few doubts 
|>-  on the following problems.
|>-   
|>-  1. Is Church-Turing thesis provable? Since we now accept 
|>-  it to be true, and have used it to prove that the Halting 
|>-  problem is unsolvable. Will one day that the C-T thesis is 
|>-  proven to be wrong? Or, can one prove that the C-T is not provable?

        The CT thesis is a statement that cannot be proved.
        Read the text book on this. Also, we did NOT use
        the CT thesis to prove that the Halting Problems is
        unsolvable. The Halting Problem is unsolvable regardless
        of whether the CT thesis is true or not.

|>-   
|>-  In the case where the C-T thesis is disproven, the 
|>-  unsolvability of Halting problem also becomes false. Is 
|>-  this correct?
|>-   
         Answered above already.

|>-  2. There is a question on C-T in your review qns for Quiz 2.
|>-  Why is the Church-Turing Thesis not proved like any other theorem.
|>-  What is expected from the answer from the student? I found 
|>-  this question quite vague.

        Read the textbook on this. This review question was meant to
        motivate student to read the textbook to find out why the
        CT thesis cannot be proved.

|>-   
|>-  Thank you for your time and hope I have no more qn to ask 
|>-  till the exam =P
|>-  ... a student ...

-------------------------------------------------------------