MHB Can Turing Machines Enumerate Union and Cartesian Product of Constructible Sets?

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion revolves around the properties of constructible enumerable sets, specifically sets $S_1$ and $S_2$. It is established that if both sets are constructible enumerable, they can be enumerated by a Turing machine. The participants confirm that the union of these sets, $S_1 \cup S_2$, is also constructible enumerable by constructing a Turing machine that alternates enumeration between elements of $S_1$ and $S_2$. Additionally, the conversation addresses how to demonstrate that the Cartesian product $S_1 \times S_2$ is constructible enumerable. It is suggested to use a pairing function, similar to the proof that $\mathbb{N} \times \mathbb{N}$ is countable, or to leverage the property that recursively enumerable sets are semidecidable and can be accepted by a Turing machine.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

We have that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is Turing machine that enumerates them, right?

To show that the set $S_1 \cup S_2$ is also constructible enumerable, we construct a Tuiring machine that enumerates alternately one element of $S_1$ and one of $S_2$.
Is this correct?

How can we show that the cartesian product $S_1 \times S_2$ is also constructible enumerable?
 
Technology news on Phys.org
mathmari said:
We have that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is Turing machine that enumerates them, right?
I am not familiar with this term. Did you mean "recursively enumerable"?

mathmari said:
To show that the set $S_1 \cup S_2$ is also constructible enumerable, we construct a Tuiring machine that enumerates alternately one element of $S_1$ and one of $S_2$.
Is this correct?
Yes.

mathmari said:
How can we show that the cartesian product $S_1 \times S_2$ is also constructible enumerable?
You can use a pairing function from the proof that $\Bbb N\times\Bbb N$ is countable. Or you can use the fact that r.e. sets are semidecidable, i.e., accepted by some TM.
 
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