A problem about computability theory

  • Thread starter iamwanli
  • Start date
  • Tags
    Theory
In summary, the conversation discusses a hypothetical scenario where A and B are effectively inseparable and B is recursively enumerable. The task is to prove that the complement of A, denoted as \bar{A}, is productive. However, the conclusion is proven to be false as it contradicts B being r.e. and not recursive. The conversation also highlights the importance of providing definitions and attempted solutions when asking homework-type questions.
  • #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
 
Physics news on Phys.org
  • #2
This isn't the place for homework. Also, when posting homework-type questions, you should state your definitions and what you've tried so far, rather than hoping that people will just give you an answer. Proper spelling and grammar wouldn't hurt either.

Anyways, what you've been asked to prove is false. Suppose [itex]B[/itex] is r.e. but not recursive. If the above were true, then we could apply it taking [itex]A = \bar{B}[/itex]. Then [itex]A[/itex] and [itex]B[/itex] are effectively inseparable because [itex]B[/itex] is not recursive, so the hypotheses are satisfied. But the conclusion, that [itex]\bar{A} = B[/itex] is productive must be false, since [itex]B[/itex] is r.e.
 
Last edited:

FAQ: A problem about computability theory

What is computability theory?

Computability theory is a branch of theoretical computer science that deals with the study of what problems can be solved by computers, and how efficiently they can be solved.

What are the main concepts in computability theory?

The main concepts in computability theory include Turing machines, computable functions, undecidable problems, and the halting problem.

How is computability theory relevant in real-world applications?

Computability theory has many practical applications in areas such as artificial intelligence, cryptography, and software engineering. It helps in understanding the limits of computation and designing efficient algorithms.

What are some famous problems in computability theory?

Some famous problems in computability theory include the halting problem, the Entscheidungsproblem, and the Church-Turing thesis.

How is computability theory related to other fields of study?

Computability theory has connections to various areas of mathematics and computer science, including logic, complexity theory, and automata theory. It also has applications in philosophy and linguistics.

Similar threads

Replies
1
Views
1K
Replies
16
Views
2K
Replies
1
Views
951
Replies
2
Views
2K
Replies
14
Views
2K
Replies
57
Views
5K
Replies
1
Views
884
Back
Top