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: 108
Yes, it's fine.
 
Ok... Thank you! (Smile)
 
Thread 'Star maps using Blender'
Blender just recently dropped a new version, 4.5(with 5.0 on the horizon), and within it was a new feature for which I immediately thought of a use for. The new feature was a .csv importer for Geometry nodes. Geometry nodes are a method of modelling that uses a node tree to create 3D models which offers more flexibility than straight modeling does. The .csv importer node allows you to bring in a .csv file and use the data in it to control aspects of your model. So for example, if you...
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
Back
Top