![]() |
|
![]() | ||
|
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 |