Google Answers Logo
View Question
 
Q: Computability and Complexity Question concerning computably enumerable sets ( No Answer,   1 Comment )
Question  
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.
Answer  
There is no answer at this time.

Comments  
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... :-)

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

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 Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy