Discussion:
A subset of a countable set
Add Reply
m***@wp.pl
2017-06-17 07:34:15 UTC
Reply
Permalink
Raw Message
On the margin of another thread.
Let's take the set of Turing's machines with halting property.
Countable?
Really?
Markus Klyver
2017-06-17 10:48:42 UTC
Reply
Permalink
Raw Message
Yes, since the set of states and the set of tape alphabet symbols both are finite.
m***@wp.pl
2017-06-17 13:12:26 UTC
Reply
Permalink
Raw Message
Post by Markus Klyver
Yes, since the set of states and the set of tape alphabet symbols both are finite.
And do You know what "countable" means?
Thomas Plehn
2017-06-17 13:29:10 UTC
Reply
Permalink
Raw Message
Post by Markus Klyver
Yes, since the set of states and the set of tape alphabet symbols both are finite.
but only for one form of the transition function
are such transition functions also countable
m***@wp.pl
2017-06-17 13:51:03 UTC
Reply
Permalink
Raw Message
Post by Thomas Plehn
Post by Markus Klyver
Yes, since the set of states and the set of tape alphabet symbols both are finite.
but only for one form of the transition function
are such transition functions also countable
The question isn't "are transition function
countable".
The question is: "is the set of Turing's
machines WITH HALTING PROPERTY countable".
Vinicius Claudino Ferraz
2017-06-17 18:47:16 UTC
Reply
Permalink
Raw Message
Yes. The set of all Pascal U C++ codes with the line: halt();
and which eventually go to that line;
is countable.
Post by m***@wp.pl
Post by Thomas Plehn
Post by Markus Klyver
Yes, since the set of states and the set of tape alphabet symbols both are finite.
but only for one form of the transition function
are such transition functions also countable
The question isn't "are transition function
countable".
The question is: "is the set of Turing's
machines WITH HALTING PROPERTY countable".
m***@wp.pl
2017-06-17 19:35:48 UTC
Reply
Permalink
Raw Message
Post by Vinicius Claudino Ferraz
Yes. The set of all Pascal U C++ codes with the line: halt();
and which eventually go to that line;
is countable.
Really?
You know, my set is infinite (obvious)
and there is no bijective function
between it and N (beczuse its construction
would require resolving halting problem).
So?
According to this
https://en.wikipedia.org/wiki/Countable_set
my set is countable and infinite, but not
countably infinite.
And according to this
https://en.wikipedia.org/wiki/Uncountable_set
it's uncountable.
Jack Campin
2017-06-17 21:18:09 UTC
Reply
Permalink
Raw Message
Post by m***@wp.pl
You know, my set is infinite (obvious)
and there is no bijective function
between it and N (beczuse its construction
would require resolving halting problem).
So, the bijection is non-constructive. Why should that be a problem?

-----------------------------------------------------------------------------
e m a i l : j a c k @ c a m p i n . m e . u k
Jack Campin, 11 Third Street, Newtongrange, Midlothian EH22 4PU, Scotland
mobile 07895 860 060 <http://www.campin.me.uk> Twitter: JackCampin
David Petry
2017-06-18 04:02:46 UTC
Reply
Permalink
Raw Message
Post by Jack Campin
Post by m***@wp.pl
You know, my set is infinite (obvious)
and there is no bijective function
between it and N (beczuse its construction
would require resolving halting problem).
So, the bijection is non-constructive. Why should that be a problem?
Here's the problem.

If you take set theory (e.g. ZFC) and attempt to translate it into natural language, and assume the logic of natural language should then apply to the set theory that has been translated into natural language, you come to the conclusion that set theory is rubbish. This has been argued ad nauseam in this newsgroup.

The pure mathematicians avoid these absurdities by asserting that mathematics has nothing to do with truth and reality, but rather, mathematics is nothing more than the game that pure mathematicians choose to play, and anyone who questions the game is a crackpot.

Maybe we should get Mueckenheim back to straighten things out.
m***@wp.pl
2017-06-18 07:25:26 UTC
Reply
Permalink
Raw Message
Post by Jack Campin
Post by m***@wp.pl
You know, my set is infinite (obvious)
and there is no bijective function
between it and N (beczuse its construction
would require resolving halting problem).
So, the bijection is non-constructive. Why should that be a problem?
Because "exist" is not a formalized term. Analyzing
it You have to use intuition. Your intuition says "such
function exists but isn't constructive".
But You have no proof. And my intuition says "no, such
function doesn't exist".
Vinicius Claudino Ferraz
2017-06-18 14:56:03 UTC
Reply
Permalink
Raw Message
Each Pascal ∪ C++ code is finite text over finite alphabet.
The countable union of countable sets is countable.
codes(1 line) ∪ codes(2 lines) ∪ codes(3 lines) ∪ ... ∪ code(human limit lines) ∪ code(robot reads during 200 years) ∪ ...
Post by m***@wp.pl
Post by Vinicius Claudino Ferraz
Yes. The set of all Pascal U C++ codes with the line: halt();
and which eventually go to that line;
is countable.
Really?
You know, my set is infinite (obvious)
and there is no bijective function
between it and N (beczuse its construction
would require resolving halting problem).
So?
According to this
https://en.wikipedia.org/wiki/Countable_set
my set is countable and infinite, but not
countably infinite.
And according to this
https://en.wikipedia.org/wiki/Uncountable_set
it's uncountable.
Dick
2017-06-18 12:08:17 UTC
Reply
Permalink
Raw Message
Post by m***@wp.pl
On the margin of another thread.
Let's take the set of Turing's machines with halting property.
Countable?
Really?
This set is countable. There is a simple construction that will list it'
Start with the TM whose Gödel number is 1. Run it for 1 cycle. If it stops, add it to the list of TMs that stop. Otherwise, record the status in list L and move to step 2.
Step 2. Add the TM with Gödel number 2 to the list L. Run every TM in L for 1 cycle. If any stop, add it to the lisy of TMs that stop.
Keep repeating this proces.
At step N, the TM with Gödel number N will be added to list L
The TM with Gödel Number n will have executed N-n steps.
Pick any TM Let its Gödel number be G.
At step G this will be added to L.
IF it stops, it will stop after some number of cycles, say g.
At stage G+g this TM will be found yo halt, and will be added to the list of TMs that halt.
Thus, the list eventually contains every TM that halts
The TMs that halt can be written in a list, and so are countable!!

Note; TMs are NOT added to the list of halters in Gödel number order. A TM with a low Gödel number may run for a vast number of cycles and then halt - or it may never halt.
There is no process like this for TMs that do NOT halt. This set is NOT countable by any recursive function; it is NOT recursively enumerable.
Dick
m***@wp.pl
2017-06-18 15:47:20 UTC
Reply
Permalink
Raw Message
Post by Dick
Post by m***@wp.pl
On the margin of another thread.
Let's take the set of Turing's machines with halting property.
Countable?
Really?
This set is countable. There is a simple construction that will list it'
:)Well done.
But the other half of Turing machines set still has
the problem.
And how about R? Cantor has proven no bijection exists.
Cantor hasn't proven no injection exists. Or has he?
Post by Dick
Start with the TM whose Gödel number is 1. Run it for 1 cycle. If it stops, add it to the list of TMs that stop. Otherwise, record the status in list L and move to step 2.
Step 2. Add the TM with Gödel number 2 to the list L. Run every TM in L for 1 cycle. If any stop, add it to the lisy of TMs that stop.
Keep repeating this proces.
At step N, the TM with Gödel number N will be added to list L
The TM with Gödel Number n will have executed N-n steps.
Pick any TM Let its Gödel number be G.
At step G this will be added to L.
IF it stops, it will stop after some number of cycles, say g.
At stage G+g this TM will be found yo halt, and will be added to the list of TMs that halt.
Thus, the list eventually contains every TM that halts
The TMs that halt can be written in a list, and so are countable!!
Note; TMs are NOT added to the list of halters in Gödel number order. A TM with a low Gödel number may run for a vast number of cycles and then halt - or it may never halt.
There is no process like this for TMs that do NOT halt. This set is NOT countable by any recursive function; it is NOT recursively enumerable.
Dick
Dick
2017-06-18 16:27:27 UTC
Reply
Permalink
Raw Message
Post by m***@wp.pl
Post by Dick
Post by m***@wp.pl
On the margin of another thread.
Let's take the set of Turing's machines with halting property.
Countable?
Really?
This set is countable. There is a simple construction that will list it'
:)Well done.
But the other half of Turing machines set still has
the problem.
And how about R? Cantor has proven no bijection exists.
Cantor hasn't proven no injection exists. Or has he?
Let us make a distinction between a "surjection" and an "injection"
A "surjection" means the set can be written in a list. Cantor's construction proves that for R no surjection exists.
However, Cantor's construction does not prove that no injection exists. If there is no way to tell whether an integer object is in the list or not, there is no way to convert the injection to a surjection; the problem is then open.
This must seem unclear. To clarify, consider the set of all Computavble Real Numbers (REC). Each has an associated TM that computes it. This TM has a Gödel number. an integer. Thus there is an injection between REC and the integers. Each member of REC has an associated integer. Thus, in this sense REC is countable
However, REC cannot be arranged as a list by ANY recursive function. If it could, then the diagonalization of REC would be a computable number and would belong in REC. Contradiction!
If you want to arrange REC as a list, you must have access to the Characteristic Function or REC (This returns TRUE if n is in REC, FALSE otherwise.)
With this you can form the list. However, this is NOT a recursive function.)
Thus REC is countable (injection) but uncountable (no recursive surjection)
There are richer sets of Real numbers than REC. They have more and more of the properties of Classical Real Numbers.
In REC not every recursively enumerable sequence has a LUB.
In the next level up, this property is true. And so on.
The study of these fields is called "Reverse Mathematica."
For detrails, se Wikepedis.
Dick
m***@wp.pl
2017-06-18 18:02:08 UTC
Reply
Permalink
Raw Message
Post by Dick
However, Cantor's construction does not prove that no injection exists. If there is no way to tell whether an integer object is in the list or not, there is no way to convert the injection to a surjection; the problem is then open.
So, I guess R can still be as countable, as REC.

Dick
2017-06-18 15:56:28 UTC
Reply
Permalink
Raw Message
Post by Dick
Post by m***@wp.pl
On the margin of another thread.
Let's take the set of Turing's machines with halting property.
Countable?
Really?
This set is countable. There is a simple construction that will list it'
Start with the TM whose Gödel number is 1. Run it for 1 cycle. If it stops, add it to the list of TMs that stop. Otherwise, record the status in list L and move to step 2.
Step 2. Add the TM with Gödel number 2 to the list L. Run every TM in L for 1 cycle. If any stop, add it to the lisy of TMs that stop.
Keep repeating this proces.
At step N, the TM with Gödel number N will be added to list L
The TM with Gödel Number n will have executed N-n steps.
Pick any TM Let its Gödel number be G.
At step G this will be added to L.
IF it stops, it will stop after some number of cycles, say g.
At stage G+g this TM will be found yo halt, and will be added to the list of TMs that halt.
Thus, the list eventually contains every TM that halts
The TMs that halt can be written in a list, and so are countable!!
Note; TMs are NOT added to the list of halters in Gödel number order. A TM with a low Gödel number may run for a vast number of cycles and then halt - or it may never halt.
There is no process like this for TMs that do NOT halt. This set is NOT countable by any recursive function; it is NOT recursively enumerable.
Dick
I fear that this is an answer to a different question.
A set is "countable" if there is a surjection between it and the integers; ie, the set can be arranged in a list. Each element of the set is in the list and can be identified by its position in the list.
In classical set theory, you are ALWAYS able to tell if an object in in a set or not. This implies that every subset of the integers is countable.
Every Turing Machine has a Gödel number that is an integer. Thus, the set of Turing Machines is countavle. Every subset of Turing Machines is countable.
In particular, K, the set of TMs that stop on their own Gödel Number is countable. ~K, the set of TMs that do not stop is also countable.
K is recursively enumerable. (This means that there is a recursive function that will form the list) Such a function was described in my earlier post. The set ~K is NOT recursively enumerable.
Dick
Loading...