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

Beware of Cranks: Misguided attempts to solve impossible mathematical problems

laphamsquarterly.org

Post reply on HN
Print view View original

31–40 of 63 posts

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#31

Post by ahartmetz »

nikanj wrote: post #11
hprotagonist wrote: post #3

> 3. They don’t understand what it means for something to be mathematically impossible. This one gets a lot of technically competent people. I spent a very unsatisfying 45 minutes vainly trying to explain to an eminent biologist that no, really, some statements really are _undecidable_ -- and no, that doesn't mean that at some future time we'll figure out a new approach that lets us decide them.

Reminds me of an infamous VC story I heard years ago: A bunch of engineers tell him that feature X is impossible due to latency, and the latency is capped by the speed of light. He challenges the team by asking them to speculate about options, if they managed to "disrupt" the industry by breaking that speed barrier, and gets mighty upset by these closed-minded engineers who are unwilling to accept any possibility of…

It could possibly be a valid question: Think about what it would do for the customer, then see if there are different solutions for some of these things. But I guess that was not how it went.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#32

Post by xyzzyz »

tathougies wrote: post #30
xyzzyz wrote: post #19

Earlier quoted context omitted.

It's clearly not true in any practical way. because most programs these days are huge beasts depending on stacks of millions of lines of code, so little can be conclusively proven about those. It's also wrong in theoretical sense, because what you're talking about is not "halting problem" at all.

I think this really depends on how much you're willing to assume. You are right of course that the general problem is intractable, because you'd end up having to analyze frameworks, system calls, kernels, etc. But if you are able to assume those function as stated, then yes, you can certainly prove limited facts. For example, the sel4 microkernel is proven correct. Part of this proof of correctness is that all system…

Sure, with some copious assumptions about the environment, you can prove without great difficulty that many real world programs do terminate. But it has really nothing to do with the Halting Problem, and saying that "halting problem is easily solved in practice" is extremely misleading.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#33

Post by SamReidHughes »

paultopia wrote: post #9
recursive wrote: post #8

Earlier quoted context omitted.

"Measuring" is not permitted. You are granted access only to an idealized compass and straight edge. There's a mobile game called Euclidea based on this which I'd recommend.

Oooh. I was imagining a compass like you're given in school, with labels on it, and ditto a ruler. :-)

That would be a protractor, which would be allowed if there were 340 degrees in a circle.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#34

Post by FakeComments »

nikanj wrote: post #11
hprotagonist wrote: post #3

> 3. They don’t understand what it means for something to be mathematically impossible. This one gets a lot of technically competent people. I spent a very unsatisfying 45 minutes vainly trying to explain to an eminent biologist that no, really, some statements really are _undecidable_ -- and no, that doesn't mean that at some future time we'll figure out a new approach that lets us decide them.

Reminds me of an infamous VC story I heard years ago: A bunch of engineers tell him that feature X is impossible due to latency, and the latency is capped by the speed of light. He challenges the team by asking them to speculate about options, if they managed to "disrupt" the industry by breaking that speed barrier, and gets mighty upset by these closed-minded engineers who are unwilling to accept any possibility of…

I’m not convinced the speed of light is a barrier when you can build a non-Euclidean quantum computer.

Maybe the VC had a point, and the engineers were overly confident in one perspective — one that had assumptions subtly different from reality.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#35

Post by BeetleB »

xyzzyz wrote: post #19
ahelwer wrote: post #18

Earlier quoted context omitted.

If you're writing business logic in a modern programming language your code can almost certainly be proven to halt. Very few people are running around coding up the Collatz conjecture or feeding programs as input to themselves.

It's clearly not true in any practical way. because most programs these days are huge beasts depending on stacks of millions of lines of code, so little can be conclusively proven about those. It's also wrong in theoretical sense, because what you're talking about is not "halting problem" at all.

Can't speak for ahelwer, but once at work we had to show (for certification purposes), that our program wouldn't get lost in an infinite loop.

Now from a realistic standpoint, all they wanted was some evidence we had considered this possibility and some data/argument to show our confidence that it wouldn't.

This was a simple program - you could confirm the algorithm wouldn't run forever by examining the code - look at the loops and their termination conditions, and look at function calls to show there were no loops in the call graph, etc. Yet one engineer in the team refused to engage. He kept invoking the halting problem. At one point I asked him that if the program was simply 'print "A"' would he still refuse to make the claim? Yup. No idea what the compiler/interpreter/HW is doing behind the scenes.

In the real world, when someone asks you to give an idea as to whether the program could hang in an infinite loop, don't invoke the Halting Problem. You're not answering the question they think they are asking, and as an engineer, your job is not to be pedantic with customers - unless you want to lose them fast.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#36

Post by vector_spaces »

While many people who become preoccupied with "problems" like these are operating in bad-faith and can't be swayed otherwise, I would be very surprised if a large number of them (if not most of them) weren't just lay people who were simply curious, who had poor experiences learning math or technical subjects growing up, and for once read about some mathematical "problem" that was accessible to them, were excited by it, and set about exploring it not realizing it was actually a red herring.

And unfortunately, if you lack a good foundation, you won't be able to realize the "problem" you're working on is actually a red-herring, and the rabbit holes you wander through when researching these "problems" will just teach you further bad habits and crankery.

For the sake of those people, I don't think it's fair or right to immediately assume bad faith and take the attitude of "run for the hills" when met with anyone who's gone down such a path. And I don't think it's right to make a mockery of them either (except of course for the ones that start trying to write books, teach seminars, or submit papers about their "discoveries" without ever getting it right).

Instead maybe we can point them towards resources so they can fix their faulty foundation and find more productive ones? No need to engage them further. Just give them something -- even something canned -- to sate the obvious curiosity that they have and give them a little direction. At the very least we can not mock them and assume bad faith -- there's nothing wrong with being curious.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#37

Post by girvo »

throwaway2048 wrote: post #12
knzhou wrote: post #2

I've talked with a bunch of cranks and my experience resonates with this article. I believe in reasoned argument and persuasion, probably to a fault, but I never managed to change any of their opinions in the slightest. One of them had a theory that every electron was made of two photons going round and round. After pointing out a few of the many problems with that he tracked down where I live to try to report me for…

You are only very rarely going to win over somebody committed to an irrational belief (who usually already holds it in plain contradiction to available facts) with logical arguments.

Said simpler: you can use logic to get someone out of a position they didn’t use logic to get into

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#38

Post by xyzzyz »

BeetleB wrote: post #35
xyzzyz wrote: post #19

Earlier quoted context omitted.

It's clearly not true in any practical way. because most programs these days are huge beasts depending on stacks of millions of lines of code, so little can be conclusively proven about those. It's also wrong in theoretical sense, because what you're talking about is not "halting problem" at all.

Can't speak for ahelwer, but once at work we had to show (for certification purposes), that our program wouldn't get lost in an infinite loop. Now from a realistic standpoint, all they wanted was some evidence we had considered this possibility and some data/argument to show our confidence that it wouldn't. This was a simple program - you could confirm the algorithm wouldn't run forever by examining the code - look a…

Yes, people who are clueless about what halting problem is, shouldn't invoke it. Halting problem is not about impossibility to prove that any specific program fails, it's about impossibility to create a program that would take any program as its input and automatically answer whether that one halts or not.

Re: Beware of Cranks: Misguided attempts to solve impossible mathematical problems

#40

Post by tathougies »

xyzzyz wrote: post #32
tathougies wrote: post #30

Earlier quoted context omitted.

I think this really depends on how much you're willing to assume. You are right of course that the general problem is intractable, because you'd end up having to analyze frameworks, system calls, kernels, etc. But if you are able to assume those function as stated, then yes, you can certainly prove limited facts. For example, the sel4 microkernel is proven correct. Part of this proof of correctness is that all system…

Sure, with some copious assumptions about the environment, you can prove without great difficulty that many real world programs do terminate. But it has really nothing to do with the Halting Problem, and saying that "halting problem is easily solved in practice" is extremely misleading.

I mean in practice the halting problem is not a useful result either so... The halting problem is theoretically solvable on every computer known to mankind becayse every computer thus far is a finite state machine, not a turing machine. The halting problem on finite state machines is solvable (exhaustively check there are no loops -- the structural recursion check I suggested above is simply an optimization of this more general technique).

Now if we are actually discussing in good faith, the halting problem is often used as a reason why a particular program analysis wont work. While a good guideline, it does not mean that there are particular classes of programs for which these analyses would work. If you can show this and show that these programs cover a good amount of useful programs, then you can construct analyses that a purely theoretical and cursory understanding of the halting problem would suggest you cant. Indeed several useful languages do just this

Post reply on HN