050.371/671 --- Formal Methods PS 1

050.371/671 - Formal Methods in Cognitive Science

Problem Set 1
Due March 15, 1999

Problem 1

Construct a Turing Machine which computes the function f(n) = 3n for n given in unary.

Problem 2

Construct Turing Machines which decide each of the following languages:

{wcw| w Œ {a,b}^*}
{w Œ {0,1}^* | w contains an equal number of 0s and 1s}

Problem 3

Let A be the language containing only the single string s, where

s = 0, if God does not exist;1, if God exists.

Is A decidable? Why or why not? (Note that the answer doesn't depend on your religious convictions.)

Problem 4

For each of the following languages, state whether it is recursive, R.E. but not recursive, or neither, and provide a proof. (Take L(M) to indicate the language accepted by M.)

L_e = {M | L(M) = ∆}
L_ne = {M | L(M) ≠ ∆}
L_a = {M | M halts on all inputs}

File translated from T_EX by T_TH, version 2.25.
On 10 Mar 2000, 18:31.