Solving Recursive Sets with Turing Machines

In summary, a recursive set is recursively enumerable if and only if the set and its complement is recursively enumerable.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

I have to show that a set is recursive if and only if the set and its complement is recursively enumerable.

I have done the following:

$\Rightarrow$
Let $A$ the recursive set, so there is a Turing machine $M$ that decides the set $A$. We construct a TM $M'$ that semi-decides the set $A$. If the TM $M$ accepts the input, then the TM $M'$ accepts the input too. If the TM $M$ doesn't accept the input, then the TM $M'$ doesn't halt on this input.
That means that there is a TM that semi-decides te set $A$. So, any recursive set is recursively enumerable.

If the set $A$ is recursive there is a TM $M$ that decides the set $A$. We construct a TM $M''$ that decides the set $A^c$. If the TM $M$ accepts the input, then the TM $M''$ doesn't accept the input and if the TM $M$ doesn't accept the input, then the TM $M''$ accepts it.

So, if the set $A$ is recursive, the complement is also recursive. So, the set $A^c$ is also recursively enumerable. That means that if the set $A$ is recursive, then the sets $A$ and $A^c$ are recursively enumerable.
$\Leftarrow$
Let $A$ and $A^c$ be recursively enumerable. That means that there are TM $M_1$ and $M_2$ that semi-decides the set $A$ and $A^c$ respectively. We construct a TM $M$ that simulates simultaneously $M_1$ and $M_2$. $M$ accepts the input if $M_1$ accepts it and rejects it if $M_2$ accepts it. Since the input is either in $A$ or in $A^c$ exactly one of $M_1$ or $M_2$ will accept. That means that $M$ will always have the output either "yes" or "no", but will never have both.

That means that there is a TM that accepts $A$. So, $A$ is recursive. Is this correct? Could I improve something?
 
Technology news on Phys.org
  • #2
Yes, this is correct. You may elaborate on "a TM $M$ that simulates simultaneously $M_1$ and $M_2$". How do you do this?
 
  • #3
Evgeny.Makarov said:
Yes, this is correct. You may elaborate on "a TM $M$ that simulates simultaneously $M_1$ and $M_2$". How do you do this?

The input of $M$, let $w$, is given simultaneously to the TMs $M_1$ and $M_2$ as inputs. One of these two machines will halt. If the machine that halts is $M_1$ the TM $M$ accepts $w$ and if it is $M_2$ then the TM $M$ rejects $w$.

View attachment 4475

Is this correct?
 

Attachments

  • TM!.png
    TM!.png
    3.1 KB · Views: 48
  • #4
Yes, it's fine.
 
  • #5
Ok... Thank you! (Smile)
 

What is a recursive set?

A recursive set is a set of inputs that can be solved by a Turing machine. It is a set that can be defined using a finite set of rules or instructions.

What is a Turing machine?

A Turing machine is a theoretical model of a computer that can perform any computation that can be performed by a physical computer. It consists of a tape, a head, and a set of rules that determine how the head moves and changes the symbols on the tape.

How does a Turing machine solve recursive sets?

A Turing machine solves recursive sets by reading and writing symbols on its tape according to a set of rules. These rules determine the machine's actions based on the current state of the tape and the symbol being read by the head. By following these rules, the Turing machine can complete any computation required to solve a recursive set.

What is the significance of solving recursive sets with Turing machines?

Solving recursive sets with Turing machines is significant because it shows that any problem that can be solved by a computer can also be solved by a Turing machine. This demonstrates the power and versatility of the Turing machine as a computational tool.

Are there any limitations to solving recursive sets with Turing machines?

Yes, there are limitations to solving recursive sets with Turing machines. While a Turing machine can solve any problem that can be solved by a computer, it may not always be the most efficient or practical solution. Additionally, there are some problems that cannot be solved by a Turing machine, such as problems that require infinite memory or unbounded loops.

Similar threads

  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
4
Views
1K
  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
989
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Programming and Computer Science
Replies
2
Views
718
  • Programming and Computer Science
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
Back
Top