Constructively proving that the integers are countable

[Asher]

Originally posted by Solver
What, do you do (advanced) non-applied math?

While CS itself is an "applied math", to at least get the degree from a reputable university you have to take many courses of "pure maths". Theory of computation is especially one field with lots of pure math.

[Elok]

Well, I can prove that integers are countable. Look: "one, two, three, four, five."

I don't think that was a particularly constructive activity, though.

[KrazyHorse]

Those aren't the integers.

[Solver]

I'd consider most of computation theory applied math, the concepts are applied in practice and exist outside the very theoretical areas. Lambda calculus, computational complexity theory and all the automata stuff, it's very much practical. I'm used to thinking of stuff such as higher-level differential calculus, abstract algebra and the like as pure maths.

[KrazyHorse]

Eh.

There's a smooth transition.

Drawing bright lines around what's pure and what's not is pretty silly.

[Asher]

Originally posted by Solver
I'd consider most of computation theory applied math, the concepts are applied in practice and exist outside the very theoretical areas.

Uhh

What?

I don't know if you know what I'm talking about.

[Elok]

Originally posted by KrazyHorse
Those aren't the integers.

Sorry, must have gotten my sets mixed up. It's been a while. Should I have said "negative one, zero, one, two, three" or "negative one, one, two, three" or what? Either way it works. Geez, you math people are slow.

[Solver]

Why wouldn't I? Computational complexity theory, for one, is definitely a concept from the theory of computation.

[KrazyHorse]

Sorry, must have gotten my sets mixed up. It's been a while. Should I have said "negative one, zero, one, two, three" or "negative one, one, two, three" or what? Either way it works. Geez, you math people are slow.

No, you need to say something like:

"0, 1, -1, 2, -2, 3, -3,..."

That's precisely the classic bijection between the ints and the naturals

[Asher]

Originally posted by Solver
Why wouldn't I? Computational complexity theory, for one, is definitely a concept from the theory of computation.

I can safely say 90% of the **** we did in theory of computation courses is never used in the real world. It's all abstract, "pure" stuff using pure math concepts...

I'd like to see you argue that, for instance, attempts to axiomatize the Church-Turing thesis is an exercise of applied math.

[KrazyHorse]

Originally posted by Solver
Why wouldn't I? Computational complexity theory, for one, is definitely a concept from the theory of computation.

So? Lie algebras are used extensively in high energy physics and discrete groups are used in solid state physics and chemistry. Does that make algebraists not pure mathematicians?

There are very very few branches of mathematics which were neither inspired by nor used by the physical sciences.

If you want to make a distinction it is better to make one in terms of rigour, not in terms of "purity".

[SlowwHand]

Seems to me that it's the math gurus that insist on counting their chickens before they're hatched.
I could be wrong, but I don't think so.

[Kuciwalker]

Originally posted by KrazyHorse
What are the precise course requirements?

If you have only 3 courses left I'm surprised because you seem to be a bit weak on algebra for that.

I have another semester of real analysis, a semester of algebra (I haven't formally taken any yet), and one more elective (which will be graph theory). I'm going to take more than those, though - I'm also done with my CS degree (sans technical writing, which I'm doing next semester), so from here on out I'm just taking whatever looks interesting. I figure I'll also take field theory and complex analysis.

I'm weak on a lot of the theory stuff 'cause I dabbled in **** like operations research early on, before I knew how boring it was. Also, a number of my compsci courses (e.g. computer algebra) give cross credit.

Then again, I've noticed that American technical undergrad requirements are significantly lower than what I'm used to (in the major, while requiring more humanities etc)

I came into uni with ~2 years worth of credit.

[Solver]

Originally posted by Asher


I can safely say 90% of the **** we did in theory of computation courses is never used in the real world. It's all abstract, "pure" stuff using pure math concepts...

I'd like to see you argue that, for instance, attempts to axiomatize the Church-Turing thesis is an exercise of applied math.

It's a fine distinction. I see your point, the attempts to axiomatize the thesis are hardly applied math, but I'd argue that the thesis, itself, is of importance as an applied math concept, given its importance for non-computable functions and its statements about the existence of recursively-defined functions. In turn, I found understanding the essentials of lambda-calculus very helpful for learning functional programming, like my first attempts at Haskell.

[Asher]

Originally posted by Solver


It's a fine distinction. I see your point, the attempts to axiomatize the thesis are hardly applied math, but I'd argue that the thesis, itself, is of importance as an applied math concept, given its importance for non-computable functions and its statements about the existence of recursively-defined functions. In turn, I found understanding the essentials of lambda-calculus very helpful for learning fuctional programming, like my first attempts at Haskell.

There's always lots of crossover.

One of the best features in the new version of C#is lambda expressions.