Constructively proving that the integers are countable

[aneeshm]

Originally posted by Kuciwalker

You mean discrete finite automaton there, not Turing machine.

???

[Felch]

Originally posted by aneeshm
In fact, the understanding of why it is necessary that there will exist an infinity of languages which will not be accepted by any conceivable Turing machine hinges on idea that no bijection can be constructed between a countably and an uncountably infinite set.

I just looked up bijection. It makes a bit more sense now. Let me see if I get this.

There's this property of infinite sets where some of them are impossible to correlate with other sets. And this property is called countability. Infinite sets which are countable, such as natural numbers, can be correlated to other infinite sets which are countable, such as perfect squares*. That's what the bijection business is.

Whereas you can not correlate natural numbers with something which is uncountable, such as "The set of all possible languages given an alphabet." These sets are both infinite, but one is more infinite than the other?

Is uncountably infinite meant to be more infinite than something that is countable, or is the property of countability independent of a set being infinite?

*I'm assuming perfect squares are countable.

[KrazyHorse]

There are two types of countability:

1) Finite
2) Infinite countable

All finite sets are countable
Some infinite sets (those which have a bijection with the naturals) are countable
Some infinite sets are uncountable

And yes, the perfect squares are bijective with the naturals so they are both infinite and countable.

The easiest bijection is 1, 4, 9, 16, ...

[KrazyHorse]

And yeah, the idea is that one infinite set can be "bigger" than the other.

In this sense the reals are "bigger" than the naturals.

[Kuciwalker]

Originally posted by aneeshm
???

Oh, hm.

The way we typically construct Turing machines (IME at CMU) is as outputting a string of symbols. Accepting languages is typically something a DFA does. However, an accept/reject construction makes sense too.

Note that your "languages a Turing machine cannot accept" corresponds exactly to the set of undecidable problems.

[TheStinger]

Is it possible to prove that breasts are countable when they are not discrete

[aneeshm]

Originally posted by Kuciwalker

Oh, hm.

The way we typically construct Turing machines (IME at CMU) is as outputting a string of symbols. Accepting languages is typically something a DFA does. However, an accept/reject construction makes sense too.

The way we were taught it, the FAs accept the languages generated by regular expressions, the NPDAs accept the languages generated by CFGs, and Turing machines semidecide the recursively enumerable languages and decide the recursive languages. We haven't covered the lambda calculus, and so haven't done the generative part of the RE and R languages. I think of them as duals - one generates, and a corresponding machine of a given type accepts.

Originally posted by Kuciwalker

Note that your "languages a Turing machine cannot accept" corresponds exactly to the set of undecidable problems.

The way we were introduced to the concept of undecidability was through the construction of the diagonalisation language, and the proof of its undecidability. The integer encoding of the Turing machines was one step of the process.

[Kuciwalker]

The way we were taught it, the FAs accept the languages generated by regular expressions, the NPDAs accept the languages generated by CFGs, and Turing machines semidecide the recursively enumerable languages and decide the recursive languages.

Yes, though those are all close to circular definitions.

The way we were introduced to the concept of undecidability was through the construction of the diagonalisation language, and the proof of its undecidability. The integer encoding of the Turing machines was one step of the process.

Formal diagonalizations is unecessarily complex and unintuitive compared to the classic proof.

Let F(x,s) be a program that, given x (a string representing a program) and s (a string representing some input to the program), returns True iff x halts on s and False otherwise. Then we can construct the program

P =
if(F(P,nil)) loop forever;
else return;

If P halts, then F(P,nil) returns True and P loops forever; if P loops forever, then F(P,nil) returns False and P returns immediately. Contradiction, therefore F cannot exist.

If you think about it, this proof is essentially equivalent to diagonalization in a different space. However, it has the advantage of illustrating a technique called a Turing jump. If we admit the program F into our programming language as an oracle, i.e. a magic instruction symbol that just behaves exactly the way F does, we don't run into the inconsistency. (Specifically, we need to define F as taking a Turing machine program as input, not a Turing machine + oracle symbol program.) We can then construct the same proof of the undecidability of the halting problem for this new, strictly more powerful computer, allowing us to admit a new oracle symbol, etc. We can do this infinitely often and thus we construct a countably infinite number of "levels" of computation. (In fact, we can show that there are an uncountably infinite number of these levels.)

[Sirotnikov]

Originally posted by Kuciwalker

You can't count (in your sense) every rational between X and Y, but the rationals are countable.

how?

[Sirotnikov]

Originally posted by Sirotnikov

how?

ok i read it up.

you set up a function to match x/y to (x,y) which is countable.
or you can setup f(m/n) = 2^m * 3^n.

this annoying, and unexpected.

but does the definition of countable not require that the matching functions be unto?

we still haven't reached it, under what subject is it usually taught?

[Kuciwalker]

Is what usually taught? The size of the rationals and the reals? The idea of countable vs. uncountable infinities?

This sort of stuff is, IME, usually covered in some sort of "intro to widely useful math" class.

[Ramo]

This is set theory. Most undergrad abstract math classes ought to at least touch on cardinality (i.e. past linear algebra).

[Solver]

If you don't have a separate set theory subject, it could be one of the topics in a discrete math course. It's not in-depth if it's just a general discrete math course, but countability should be touched upon.

[aneeshm]

Originally posted by Kuciwalker

The way we were taught it, the FAs accept the languages generated by regular expressions, the NPDAs accept the languages generated by CFGs, and Turing machines semidecide the recursively enumerable languages and decide the recursive languages.

Yes, though those are all close to circular definitions.

Quite right.

Originally posted by Kuciwalker

The way we were introduced to the concept of undecidability was through the construction of the diagonalisation language, and the proof of its undecidability. The integer encoding of the Turing machines was one step of the process.

Formal diagonalizations is unecessarily complex and unintuitive compared to the classic proof.

Let F(x,s) be a program that, given x (a string representing a program) and s (a string representing some input to the program), returns True iff x halts on s and False otherwise. Then we can construct the program

P =
if(F(P,nil)) loop forever;
else return;

If P halts, then F(P,nil) returns True and P loops forever; if P loops forever, then F(P,nil) returns False and P returns immediately. Contradiction, therefore F cannot exist.

That was the proof we did, from Hopcroft/Ullman/Motwani.

The proof included a section on how to encode an entire Turing machine as an integer, and how another could be set up as a universal TM which, when given a TM and an input string, would simulate the operation of the given TM on the given input. We then considered the question of how this hypothetical machine would behave if it were programmed to halt when the input machine didn't, and not halt when it did, and the contradiction this resulted in when it was fed itself as input - essentially the same as your proof.

Just out of curiosity, which book did you use for this course?

Originally posted by Kuciwalker

If you think about it, this proof is essentially equivalent to diagonalization in a different space. However, it has the advantage of illustrating a technique called a Turing jump. If we admit the program F into our programming language as an oracle, i.e. a magic instruction symbol that just behaves exactly the way F does, we don't run into the inconsistency. (Specifically, we need to define F as taking a Turing machine program as input, not a Turing machine + oracle symbol program.) We can then construct the same proof of the undecidability of the halting problem for this new, strictly more powerful computer, allowing us to admit a new oracle symbol, etc. We can do this infinitely often and thus we construct a countably infinite number of "levels" of computation. (In fact, we can show that there are an uncountably infinite number of these levels.)

Quite interesting. Where can I read further on this?

[KrazyHorse]

The classic demonstration of the countability of the rationals is as follows:

for every rational there is a unique reduced representation p/q where p and q are mutually prime

Order the rationals in a grid with p on the horizontal axis and q on the vertical. List them in order of p+q, skipping the ones which have already been represented:

0, 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1,...

This is a bijection because every rational p/q will eventually be represented (to a lazy approximation by the (p+q)^2 th term) and each is only represented once.