![]() |
|
|
| Subject:
Computability and Complexity Question concerning computably enumerable sets
Category: Reference, Education and News Asked by: lisa80-ga List Price: $50.00 |
Posted:
09 Sep 2003 13:07 PDT
Expires: 13 Sep 2003 08:40 PDT Question ID: 253944 |
Hi, I have four questions questions (proof by induction is prefered,
but other methods will do):
1. Show that {0, 1}* is computably enumerable.
2. Prove that an infinite language is computably enumerable if and
only if there is a computable function that enumerates it without
repetition.
3. Prove that a set is decidable if and only if there is a one-to-one
computable function which enumerates its elements in increasing order.
4. Prove that a function f is computable if and only if it's graph
{(x, f(x))} is computably enumerable. |
|
| There is no answer at this time. |
|
| Subject:
Re: Computability and Complexity Question concerning computably enumerable sets
From: baylink-ga on 11 Sep 2003 12:43 PDT |
Left as an exercise for the student... :-) |
If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you. |
| Search Google Answers for |
| Google Home - Answers FAQ - Terms of Service - Privacy Policy |