- #1
iamwanli
- 2
- 0
Soppose that A,B are effectively inseparable,B is r.e,then how to prove that [tex]\bar{A}[/tex] is productive
A problem about computability theory
- Context: Graduate
- Thread starter iamwanli
- Start date
-
- Tags
- Theory
Click For Summary
SUMMARY
The discussion centers on the proof regarding effectively inseparable sets A and B, where B is recursively enumerable (r.e.). It concludes that the assertion that the complement of A, denoted as \bar{A}, is productive is false. The reasoning provided indicates that if B is r.e. but not recursive, then the conditions for effective inseparability do not lead to a productive complement. Specifically, setting A as \bar{B} demonstrates the contradiction, affirming that \bar{A} cannot be productive if B remains r.e.
PREREQUISITES- Understanding of effectively inseparable sets in computability theory
- Knowledge of recursively enumerable (r.e.) and recursive sets
- Familiarity with the concept of productive sets in computability
- Basic proficiency in formal logic and mathematical proofs
- Study the properties of recursively enumerable sets and their implications
- Learn about effective inseparability and its applications in computability theory
- Explore the concept of productive sets and their role in computability
- Review formal proofs in computability to strengthen understanding of logical reasoning
Students and researchers in theoretical computer science, particularly those focused on computability theory and mathematical logic.