#math - Sat 3 Mar 2007 between 00:00 and 00:33

NY Lost Funds



TRWBWihope: the only non-math thing about computer science is that it's mostly elementary math instead of deep math, but hell, it's 40 years old. how deep was geometry 40 years after the first guy drew a triangle?
klafkaisn't computer science just a part of discrete math really?
ihopeThat's what I'd say, yes.
DacicusWhat's discrete math cover?
LoganCapaldoI'd say it depends how you squint at it
ihopeAlso, I might have discovered a big mathy paradox. But I probably didn't.
Dacicusyay, paradox
ihopeBig mathy question #1: is there a sequence of ordinal numbers that exceeds all of them?
TRWBWihope: maybe you mean http://en.wikipedia.org/wiki/Burali-Forti_paradox
ihope...Indeed there isn't.
TRWBWDacicus: traditionally discrete math was a grab bag course of a bit of combinatorics, number theory, lattice theory, graph theory, and set theory. i don't think it was ever considered a "field"
klafkathings dealing in discrete numbers?
TRWBWit was a halfway course between the calculus non-math people took and the things like number theory and abstract algebra that math majors took
klafkayeah
ihopeWell, anyway, the paradox goes as follows: let's define A_n = the smallest ordinal number that is not a recursive ordinal, except using a class-n machine instead of a Turing machine, where a class-n machine is a Turing-machine plus the ability to solve the halting problem for all class-m machines where m < n.
Then the iffy and probably incorrect part: A_n is always countable, but A_n > A_m if n > m. Therefore, the ordinal numbers can be mapped one-to-one with the countable ordinal numbers.
TRWBWihope: i got no idea what you are saying, but i got a neat proof of the incomputability of the halting problem
ihope"A_n is always countable, but A_n > A_m if n > m" would be the part that's probably wrong.
TRWBW: diagonalization is fun, aye?
TRWBWihope: it's a different proof than that or the standard one
ihope: and as far as i know, it's my own
ihopeSounds interesting.
TRWBWihope: the inspiration is to connect proofs of the halting problem to classical paradoxes
ihope: diagonalization proof goes to russels paradox
ihope: the standard proof goes to the paradox of "this statement is false"
ihope: my proof is based on the paradox "x is the smallest number that requires more than 100 characters to describe"
DacicusTRWBW: You said, "traditionally." What does discrete math cover now?
TRWBWso basically, you ask for the smallest number that requires a turing machine of length greater than n to generate it. but if you have a turing machine that solves the halting problem, you can construct a machine of size m+log(n) (or smaller) that computes the number that needs a turing machine of size n to compute it.
Dacicus: no idea. maybe the same thing, maybe something else, i haven't actually looked at the syllabus of a discrete math course in more than 20 years
ihopeTRWBW: ah. Sounds fun :-)
TRWBWi told it to Gregory Chaitan in the mid 80's and he thought he hadn't heard it before, so i felt clever.
LoganCapaldoas o 2 or so years ago it covered the same stuff
(Discrete math)
at least where I go
oh and logic was in the grab bag too
ihopeSo is the order type of a non-degenerate real interval [a,b] the same no matter what a and b are?
TRWBWihope: um, what's an order type? and what's a degenerate interval?
ihope: i'm pretty fuzzy on the abstract stuff
ihopeAn order type is essentially the order they're in, rather than them themselves.
TRWBWihope: so an equivalence class under order isomorphism?

Page: 2 9 16 23 30 

IrcArchive

NY Lost Funds