m***@wp.pl

2017-06-17 07:34:15 UTC

Permalink

On the margin of another thread.Raw Message

Let's take the set of Turing's machines with halting property.

Countable?

Really?

Discussion:

(too old to reply)

m***@wp.pl

2017-06-17 07:34:15 UTC

Permalink

On the margin of another thread.Raw Message

Let's take the set of Turing's machines with halting property.

Countable?

Really?

Markus Klyver

2017-06-17 10:48:42 UTC

Permalink

Yes, since the set of states and the set of tape alphabet symbols both are finite.Raw Message

m***@wp.pl

2017-06-17 13:12:26 UTC

Permalink

Raw Message

Yes, since the set of states and the set of tape alphabet symbols both are finite.

Thomas Plehn

2017-06-17 13:29:10 UTC

Permalink

Raw Message

Yes, since the set of states and the set of tape alphabet symbols both are finite.

are such transition functions also countable

m***@wp.pl

2017-06-17 13:51:03 UTC

Permalink

Raw Message

Yes, since the set of states and the set of tape alphabet symbols both are finite.

are such transition functions also countable

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

Permalink

Yes. The set of all Pascal U C++ codes with the line: halt();Raw Message

and which eventually go to that line;

is countable.

Yes, since the set of states and the set of tape alphabet symbols both are finite.

are such transition functions also countable

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

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.

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

Permalink

Raw Message

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).

-----------------------------------------------------------------------------

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

Permalink

Raw Message

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).

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

Permalink

Raw Message

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).

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

Permalink

Each Pascal ∪ C++ code is finite text over finite alphabet.Raw Message

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) ∪ ...

Yes. The set of all Pascal U C++ codes with the line: halt();

and which eventually go to that line;

is countable.

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

Permalink

Raw Message

On the margin of another thread.

Let's take the set of Turing's machines with halting property.

Countable?

Really?

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

Permalink

Raw Message

On the margin of another thread.

Let's take the set of Turing's machines with halting property.

Countable?

Really?

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?

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

Permalink

Raw Message

On the margin of another thread.

Let's take the set of Turing's machines with halting property.

Countable?

Really?

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?

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

Permalink

Raw Message

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.

Dick

2017-06-18 15:56:28 UTC

Permalink

Raw Message

On the margin of another thread.

Let's take the set of Turing's machines with halting property.

Countable?

Really?

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

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...