Home
Homework
Index
Syllabus
URM Simulator
Extra Homework Problems
Models of Computation - Mathematics 450 - Spring 2005
For HW #20
Let f be a unary computable function. Let A = {x | x is an index of f}. Is A recursive? Prove your answer.
Is "E
x
is infinite" partially decidable? Prove your answer.
How about "E
x
is finite"? Prove your answer.
How about "W
x
is infinite" and "W
x
is finite"? Prove your answers.
Is "
j
x
=
j
y
" partially decidable? Prove your answer.
Is "
j
x
¹
j
y
" partially decidable? Prove your answer.
Updated: 31 August, 2009 17:44:19