# User:IssaRice/Computability and logic/Characterization of recursively enumerable sets

From Machinelearning

Let be a set of natural numbers. The following are all equivalent.

Property | Emphasis |
---|---|

The elements of can be enumerated in a computable manner as | Recursively enumerable |

is the range of a computable partial function. | Recursively enumerable |

is empty or the range of a computable total function. | Recursively enumerable |

is empty or the range of a primitive recursive function. | Recursively enumerable |

is the domain of a computable partial function. | Semi-ness |

A recursive semicharacteristic function for exists. | Semi-ness |

There exists a two-place recursive relation such that | Semi-ness |

The relation is , i.e., there exists a -place recursive relation such that | Semi-ness |

The relation has a computable partial verifying function, i.e., there exists a computable partial function such that .^{[1]} |
Semi-ness |

The rows labeled "Recursively enumerable" all emphasize the fact that is "recursively enumerable", i.e., that the elements of can be listed in a recursive (computable) way.

The rows labeled "Semi-ness" all emphasize the fact that is semidecidable/recognizable/verifiable/semirecursive, i.e., that if something is in , then in a finite amount of time we can verify this computably, but that if something isn't in , then we will run into an infinite loop.

The fundamental theorem of recursively enumerable sets says that recursively enumerable equals semi-ness.