Week 11 - Halting and computable enumerable

Question 1

What does it mean for a language
L to be computably enumerable (C.E.)?

Answer 1

A language L is C.E. if there is a machine M that is sound (if M(w) = 1, then w is in L) and complete (if w is in L, then M(w) = 1).

Question 2

Is a decideable language computably enumerable

Answer 2

Deciable:
sound
complete
terminating

Yes since it has the two properties we need sound and complete

Question 3

what does computeably enumarable guarantee in terms of when faced with :
accepting string
rejecting string

Answer 3

remember :
its sound And complete (complete is what we will be focusing on here

Complete tells us for accepting strings
if w exisists in L => M(w) = 1

so machine is will eventually halt

but there is no such guarantee for words not in L :
which may halt and reject
or loop forever

Question 4

What does it mean for a language
𝐿
L to be co-computably enumerable (co-C.E.)?

Answer 4

A language L is co-Computable enumerable if its complement is computably enumerable.