MHB Solving Recursive Sets with Turing Machines

AI Thread Summary
The discussion focuses on proving that a set is recursive if and only if both the set and its complement are recursively enumerable. The initial argument establishes that if a set A is recursive, a Turing machine (TM) can be constructed to semi-decide A, confirming that recursive sets are recursively enumerable. It further demonstrates that if A is recursive, its complement A^c is also recursive and thus recursively enumerable. The reverse direction is addressed by assuming both A and A^c are recursively enumerable. A TM is then constructed to simulate both TMs that semi-decide A and A^c simultaneously. This TM will accept or reject based on which of the two TMs halts, ensuring a definitive output. The conclusion confirms that if both A and A^c are recursively enumerable, A must be recursive. The correctness of the arguments is affirmed, with a request for clarification on the simultaneous simulation of the TMs, which is subsequently explained.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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
Yes, this is correct. You may elaborate on "a TM $M$ that simulates simultaneously $M_1$ and $M_2$". How do you do this?
 
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: 107
Yes, it's fine.
 
Ok... Thank you! (Smile)
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
Back
Top