Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Mathematical Hacker (2012)

evanmiller.org

Post reply on HN
Print view View original

151–160 of 186 posts

Re: The Mathematical Hacker (2012)

#151

Post by hnews_account_1 »

constantcrying wrote: post #143
kaashif wrote: post #126

Earlier quoted context omitted.

The fact that you have found a function of type () -> () is a proof that true implies true. This is the Curry-Howard isomorphism. Not a particularly interesting proof.

But surely there are uncomputable objects which you can make mathematical statements about. How do you encode them into a type signature?

There are no closed form solutions to uncomputable problems. You can encode them in math. You can also encode them in a program. The result is the same.

In fact, the absolute limit of computability is so interesting that people have explored it in the abstract sense. For reference, see busy beaver numbers on Wikipedia or Scott aaronson’s awesome essay on finding the bigger number.

Re: The Mathematical Hacker (2012)

#152

Post by defrost »

hnews_account_1 wrote: post #150
constantcrying wrote: post #52

Earlier quoted context omitted.

>All those symbols you see map to a set of steps (a program.) Simply not true. Most mathematical statements, e.g. proofs of existence have no relation to a "program". >math is geared and targeted for people who like doing symbolic logic by hand. No, it is not. There is absolutely nothing interesting about symbol manipulation, it is always the least interesting part of a proof. It usually is the part the author handwa…

The first part of your answer is incorrect about programming in a general sense (not the particular software programming most of HN does). I push it so far back as to call it programming in a computer science sense, which is very simply just proof theory encoded into a system. There is a reason Turing is considered one of the greatest minds to ever live. He didn’t just invent a concept. He invented a completely new b…

Errr, Alonzo Church solved it first, Turing followed .. and both of their independent methods were heavily based upon similar earlier work by Kurt Gödel, with Church also incorporating ideas from Stephen Kleene.

There is no doubt that Turing was bright, very bright indeed, but next you'll be claiming he cracked the Enigma Code or something.

Re: The Mathematical Hacker (2012)

#153

Post by eternityforest »

dysoco wrote: post #53
bmitc wrote: post #9

In Steve Yegge’s linked post: > Math is a lot easier to pick up after you know how to program. In fact, if you're a halfway decent programmer, you'll find it's almost a snap. This couldn’t be more wrong. Mathematics is the hardest thing I have ever done. I’m sorry, but mathematics is orders of magnitude more intensive and difficult than most programming. A simple fact that shows this is the amount of programmers who…

> mathematics is orders of magnitude more intensive and difficult than most programming But what level of programming and mathematics are you comparing here though? because college-level algebra and calculus is really not that hard imho (once it "clicks" for you, but it's the same for programming), and if we are comparing math as in what you see in a BSc/Msc of Mathematics (or research-level) then I agree it's hard b…

For practical purposes, a fair comparison would be "a useful amount of programming" vs "A useful amount of math".

You can get hired after a brief boot camp, although it's not common.

A useful amount of math is like, ordinary differential equations in engineering school, since apps have taken over most use cases for simpler math.

The only direct use is to learn to access the "New way of thinking" math people talk about, and even that seems harder than making detailed to do lists.

Re: The Mathematical Hacker (2012)

#154

Post by eternityforest »

bmitc wrote: post #9

In Steve Yegge’s linked post: > Math is a lot easier to pick up after you know how to program. In fact, if you're a halfway decent programmer, you'll find it's almost a snap. This couldn’t be more wrong. Mathematics is the hardest thing I have ever done. I’m sorry, but mathematics is orders of magnitude more intensive and difficult than most programming. A simple fact that shows this is the amount of programmers who…

The only thing comparable is maybe drawing or playing an instrument. Math can never be learned from a textbook.

Anything that's just algorithmic steps would be done by a computer, so the useful math people want to learn requires some kind of insight or new mode of thought, or advanced methods that have not been made into an app yet.

I suspect when people say math is easy, they mean arithmetic and pre-algebra, and they're not concerned with practical applications at all, just the idea of general education and new ways of thought, and who knows if the level of math they are talking about is even enough to indirectly do much in daily life.

Re: The Mathematical Hacker (2012)

#155

Post by eternityforest »

geysersam wrote: post #114
nickelpro wrote: post #69

Earlier quoted context omitted.

I would hard disagree that undergrad level Analysis or even just the trickier corners of vector calculus are within the bounds of what programmers can easily pick up without dedicated and guided study. Everybody's gangster until they have to parameterize some bullshit helical structure in R3. Comparable levels of programming, what we expect of CS juniors, are regularly picked up by "the guy who is good with Excel" in…

I think you're hitting the nail on the head here. Something about the learning process makes programming much easier to pick up. What if we had something similar for mathematics? Rapid feedback, error messages, maybe even linters and highlighting for the "mathematical syntax". I've though about this before and I think tools like this could unlock math for a lot of people, and also increase the effectiveness of profes…

Is it the learning process, or the subject itself?

Programming works with manmade abstractions, carefully designed to have very few interactions, keep mutable state contained, and to have all the parts structured in a hierarchy without recursion.

In math you have systems of equations that all reference each other. And they all happen at the same time because there's no steps and time or lines of code just 5 equations that all interact.

The atomic pieces are much larger and tied together and it inherently seems to require being able to fit nontrivial ideas in your head.

Programming lets you design a complex architecture one tiny piece at a time without considering other pieces.

Re: The Mathematical Hacker (2012)

#156

Post by eternityforest »

__MatrixMan__ wrote: post #140
geysersam wrote: post #114

Earlier quoted context omitted.

I think you're hitting the nail on the head here. Something about the learning process makes programming much easier to pick up. What if we had something similar for mathematics? Rapid feedback, error messages, maybe even linters and highlighting for the "mathematical syntax". I've though about this before and I think tools like this could unlock math for a lot of people, and also increase the effectiveness of profes…

I'd love to play around with such tools, but I think they'd only get you so far before they'd start to become a hinderance. The linter in mathematics is whether the other mathematician (whoever you're proving to ) knows what you mean. If you're locked into a rigidly defined syntax, an obvious line of questioning is: what's not expressible in this syntax? I fear that by the time the tooling was agreed on, built, and t…

If you're learning math for career reasons rather than just pure curiosity, engineering is the main/possibly only place you'd use it besides statistical analysis.

Re: The Mathematical Hacker (2012)

#157

Post by mschoenert »

bibanez wrote: post #149
mschoenert wrote: post #82

Earlier quoted context omitted.

My thoughts at this point in the original article was: Well - if you want to demonstrate how mathematics helps here, then you should mention that computing the n-th fibonnaci number can be computed as the n-th power of the matrix [[1,0],[1,1]], and that the most efficient way to compute powers (in any associative domain) is the repeated squaring algorithm.

There are many ways to obtain the formula mentioned in the article. One of them is by diagonalizing this matrix and then applying exponentiation. How can another algorithm be better than constant time in the most general case?

No - there isn't really an O(1) solution. And the reason is that the Fibonacci numbers grow without limit. So there can't be an O(1) algorithm - even just writing down the answer takes O(N) - because the answer has O(N) bits.

Concretely Fibonacci(1480) is the largest Fibonacci number that fits into a double. So for higher Fibonacci numbers you need to compute this with arbitrary size integers (or floats). And then look at it in terms of bit complexity (i.e. the time to compute a product grows with the size of the integers).

Put differently. The "constant time" algorithm only works for N up to 1480. And if you limit N, then it doesn't really make sense to talk about the asymptotic complexity.

I believe the optimal algorithm is to compute the Fibonacci number by computing the N-th power of the matrix [[1,1],[1,0]], and compute the power using the repeated squaring algorithm. There are alternative formulations of that using identities for Fibonacci or Lucas numbers, but those identities basically correspond to squaring the matrix.

If you really want the asymptotically fastest algorithm you must use the fastest algorithm for integer multiplication (Harvey and van der Hoeven’s).

But even with the naive multiplication for arbitrary size integers you can compute Fibonacci(1000000) - which is a number with more than 200'000 digits - in less than a second. ;-)

Re: The Mathematical Hacker (2012)

#158

Post by eternityforest »

nextos wrote: post #97
nickelpro wrote: post #80

Earlier quoted context omitted.

I would quibble with whether this is exactly equivalent. In programming I knew I needed to sort a list or find a most efficient path because some practical problem I was trying to solve demanded that I do that. Frequently I had a basically crap but working independent solution before I learned the names "EWD" or "A*". I independently discovered that I needed virtual interfaces (before I knew them by that name, "I wis…

I think your comparison is a bit unfair. Essentially, CS is as hard as mathematics because it is mathematics. For example, take any good static analyzer that implements abstract interpretation. It generally works using Galois connections, which is just abstract algebra. Dijkstra's algorithm or A* came pretty early in the history of CS. It would be fair to compare their difficulty to something similar in mathematics,…

A* is already intermediate level programming. CS is math because it's what we call the parts of programming that are math.

But so much of programming isn't. It doesn't require deep understanding, static analysers are advanced level things that are way beyond what many working programmers ever encounter.

I can't say I've ever seen "Real math" myself.

Re: The Mathematical Hacker (2012)

#159

Post by stealthcat »

Seems like the so called Lisp hackers are Common Lisp users.

Before Matlab was cool, Lisp is VERY maths-heavy and engineering-heavy. Symbolic equation solvers, robot controls, neural nets, etc.

Even Julia which is very Matlab-like has roots to Lisp.

Post reply on HN