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.

A "crank" is a very specific type of person, who will not heed any constructive criticism and in fact deliberately avoids resources from the establishment. Any dismissal is viewed as a conspiracy by the establishment to keep their brilliant ideas from dismantling the establishment's sacred cows.

Like concern trolls, their goal is seemingly to waste the time and energy of anyone willing to listen or engage, except they're not doing it wittingly, so you just wind up feeling like a jerk when you inevitably have to ignore their latest 20-page ramble and get some real work done.

Thank you for a comment coming from a position of genuine compassion for people who may not have had many opportunities in their life to train their minds.

The description of cranks as old, retired males with a minimal mathematical background given by U. Dudley seems to agree with what you say, btw.

As they say, sounds good, doesn't work. You can tell the genuinely curious sort from true cranks at a glance, and this article is about the latter. Every academic has interacted with far too many true cranks.

I always try to give rebuttals that are accessible, explaining in plain English what is going wrong and giving resources for follow-up learning. It doesn't work -- you get "that's cute, you still believe in textbooks, when I've proven them all wrong."

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 "censorship".

I think the best way of dealing with nonsense in Internet forums is to give a single reply, and then go away. Getting dragged into an ongoing "discussion" is unlikely to be worth the effort, since such people typically resort to rejecting evidence and making ad hominem attacks.

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.

I completely agree. But might some fraction of such people be “won over” by methods other than logic? Asking them how they got interested, perhaps, and drawing out what in their past caused them to become so obsessed?

Or even by redefining the goal of the debate?

It may be that I’m giving too much credit and most are truly hopeless. But so often with “people problems” I’ve seen approaches work beautifully and which in retrospect seem obvious. But in the moment I would never have thought up because I was considering things so narrowly.

In my experience, most of these people are over twice my age and slip into condescension the second I stop laying down logical arguments. If I don't argue against them logically, they invariably walk away triumphant, thinking they've just educated some ignorant young man. It makes the problem worse, so I might as well not talk with them at all.

In any case, their stories are all remarkably similar...

I agree with the main argument but would like to note "crank" in not an all or nothing description. Sometimes the problem as publicized doesn't exactly match the precise problem. For example you can trisect an arbitrary angle if allowed an infinite number of steps. Sometimes the problem is in breaking the abstraction layer. For example one of my kids thought you could make arbitrarily slow motion videos by taking slow motion videos of slow motion videos. And that brings up the issue of how to handle a crank. I loved that my son thought through the video issue and didn't want to inhibit future thinking. We ran some experiments taking video of the tv and it was fun. Sometimes people won't accept counter arguments and evidence (sometimes that person is me) and there's a time to move on. Still, in my experience few people are true die hard cranks and most people respond well if given the right direction.

> 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 a breakthrough

Well, MOSH breaks through the speed of light latency limitation of SSH by ... predicting the server's response.

Although the laws of physics can't be broken, in certain scenarios we can simulate we have done just that. And often that's just what you need to get ahead of your competition.

"You're saying we can't do HFT between Tokyo and New York faster than the speed of light? Here's a completely unrelated product, that does something completely different, and the limit they're working with doesn't really apply to us. So it is possible! Maybe you should go to Burning Man, that would open your mind.."

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.

There's a flipside of this, where people incorrectly lord "mathematical impossibility" over others as a way to shut down discussion. You see this on the topic of cryptographic backdoors especially. I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position.

The interface between plain language and math is messy. I don't think I've ever seen something suggested that was actually mathematically impossible. Even the halting problem is easily solved in practice.

This is where a very carefully worded description of the problem may be required.

Cryptographic backdoors are possible (See Clipper and LEAF for previous examples). Cryptographic backdoors that will only ever be used "legitimately" aren't, and legitimacy isn't a mathematical concept.

> Even the halting problem is easily solved in practice.

You don't grok what the halting problem is. What you're describing (I assume) is determining if a specific program is going to terminate. That's not the same problem.

From Wikipedia:

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

The entire field of static analysis is "solving" undecidable problems effectively and productively all the time. Just accept a few false positives or false negatives and suddenly the field opens up to be amazingly useful.

Yes it isn't literally solving the halting problem. But I've had a weird number of people tell me that the stuff I work on doesn't work because of things they learned in undergrad.

I "grok" very well what the halting problem is, thank you. It's colloquially used in the sense of being unable to tell whether a program terminates. For reference I direct you to early static analysis tool promo materials (ex. Coverity) which usually explicitly address the "doesn't this run into the halting problem?" question given its common occurrence.

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.

In a company I worked for, systems were brought to their knees because of a while loop that went infinite under poorly tested conditions. There was a meeting and the head of the dev team came down to tell us that, in the meeting, it was decided that we should not use iteration any more because it runs the risk of going infinite. Instead, we should use recursion for all our looping needs.

That was in a C# shop so of course the "decision" was never implemented. My guess is that this was a completely mad decision taken by non-technical managers in a moment of panic, who had pressed our tech lead a bit too much on why software breaks and what can be done to avoid it breaking- and then latched on to some off-hand comment about recursion being an alternative to iteration, and ran with it.

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.

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 calls do terminate.

But, actually, the most straightforward way to show that most 'everyday' programs terminate is -- assuming functionality of the language runtime as stated -- that they typically consist of non-recursive functions or functions on structurally smaller inputs. It would be obnoxious, but not difficult to show that a program like 'grep' terminates, assuming functionality of the operating system and hardware on which its running. This is actually fairly straightforwards, and many many functional languages with a focus on correctness have totality checking builtin. For example, Idris and Agda.

Of course, if you're going to ask to prove both functionality of the operating system (like Linux + glibc) or the processor itself, then that could indeed be trickier. But, if you limit your stack, it's certainly possible. The truth is that most computing does not consist of solving Turing complete problems.

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

This comment is not germane to the point you were making, just wanted to share:

I am a web dev who knows nothing of the Collatz conjecture, so I had to check out the Wikipedia article for it. Thanks for teaching me something today.

I wrote this JavaScript function based on what I read in the article. It's a simple algorithm but it was fun to see it work. For anyone who is in my shoes (weak mathematical background), running this function might be a useful supplement for illustrating the gist concept of the Collatz conjecture:

function collatz(i) {
console.log(i); // for visual feedback
if (i <= 0) throw new Error('Input must be a positive integer');
if (i === 1) return i;
if (i % 2 === 0) return collatz(i/2);
return collatz((3*i)+1);
}
collatz(42); // or any positive integer

That's not what the OP means, from what I can tell, but in the real world even a program like "while true {}" can be guaranteed to halt because eventually someone will figure out it's stuck in an infinite loop and abort it.

(tongue in cheek, of course, but I think the OP is trying to capture a similar pragmatic view of the halting problem)

If you can put the points of the compass against the straightedge, which gives you a marked straightedge, you can trisect an angle. But that's considered cheating. Archimedes is credited with figuring out this approach.

I used to answer correspondence for the EFF Cooperative Computing Awards (which are an actual financial prize for finding very large primes) and people who wrote in were almost uniformly either kids or people meeting all of the criteria mentioned here.

Almost none of them thought it was important to understand any prior results about primality testing before submitting a claim for the prize, while a majority didn't seem comfortable with the idea of a mathematical proof or theorem. In general, they didn't have a sense that some properties are always true, some are never true, and some are sometimes true and sometimes not true, and that mathematical reasoning can often definitively establish which of these categories a particular property is in.

"Beware of Cranks" shows a terrible understanding of how major progress in science and technology happens. If you go around flipping the "crank bit", sure, you will save yourself spending time evaluating lots of correct negatives and have more time to make on incremental progress, but you will also have a couple of false negatives, one or two of which will go on to change the world. World change is dominated by black swans.

Conversely, Thiel's Hereticon conference idea is brilliant and shows a terrific understanding of how progress in science happens.

I wonder if Andrew Wiles had taken a different approach when announcing he had solved Fermat's Last Theorem if he would have been considered a crank. I would imagine that problem would have attracted nonsense solutions prior.

That's a big hypothetical, though. Andrew Wiles had been producing sensible mathematics in the community already, so there was no reason to suspect him of being a crank. Also, his proof did not emerge in a vacuum, he pursued approaches that were already known to be connected to FLT.

As for FLT attracting nonsense solutions: Yes, plenty of them. It being such a simply stated problem, and immediately understandable to laypeople certainly exacerbated the problem.

Fair point I have no familiarity with his earlier work, or even that there was suspicion of a connection, I did mean for my point to be a bit more general, just seemed like a reasonable example

Super curious---I actually never took trig (complicated story), so I don't understand the trisecting an angle thing at all. What is it that makes measuring the angle and then dividing that measurement by 3 impossible?

"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.

While dividing by three is easy, dividing an angle by three with just a compass and a straight edge is impossible. Numberphile[1] did a video on this a few years ago

An important aspect of this isn't that you cant trisect any particular angle, its that you cant trisect any arbitrary angle, plenty of angles, like 90 degrees, are trivial to trisect.

Yes. The better way to phrase it would be that some angles are impossible to construct, and importantly that includes a trisection of some angles that can in fact be constructed.

The "compass" and "straightedge" are (nowadays) just a colorful/concrete way to describe the problem. When mathematicians consider this, they phrase the conditions in such a way that no physical "compasses" or "straightedges" are involved.

For example, you might say: (1) If you have 4 different points P, Q, R, S so that the lines PQ and RS are not parallel, you may "acquire" their point of intersection; (2) If you have 4 different points P, Q, R, S and the circle with center P and radius PQ intersects the line RS then you may "acquire" the point(s) of intersection of the circle and the line; (3) If you have 4 different point P, Q, R, S and the circle with center P and radius PQ intersects the circle with center R and radius RS, you can "acquire" the intersection point(s) of the circles. ("Acquire" a point means roughly that your number system now contains the coordinates of the point.)

Notice that this removes the problem of people doing unintended tricks with or drawing horribly complicated diagrams with physical compasses or straightedges, and makes mathematically precise what is allowed.

The following is probably more than you want to know, even though I'll omit lots of the details. The idea is that circles are defined by quadratic equations, and lines by linear equations. At every step, you're solving (acquring the roots of) simultaneous linear or quadratic equations. Starting with the rational numbers, as you "acquire" new points, you "extend" the rationals to bigger fields "by extensions of degree 1 or 2". Since degrees multiply, at any point, you've "extended" the rationals by a total degree 2^n.

So the result is: Theorem. Any point you construct must (a) lie in an extension of the rationals of degree 2^n; (b) be algebraic, in the sense that its coordinates are roots of rational polynomials.

Now take something like trisecting a 60 degree angle. A third of 60 is 20, and to construct a 20 degree angle you need to construct t = cos 20 degrees. But from trig, t is a root of x^3 - 3 x - 1 (which is irreducible over the rationals), so t has degree 3 --- and 3 is not a power of 2. Hence, a 60 degree angle can't be trisected.

Squaring the circle means given a circle, construct (the side of) a square with the same area. Take the circle to have radius 1, so its area is pi. The square you need would have side pi^(1/2), but pi (and pi^(1/2)) isn't algebraic in the sense noted above. (Lindemann showed pi is transcendental.) So you can't square an arbitrary circle.

Duplicating the cube means given a cube (say with sides of length 1), construct (the side of) a cube whose volume is twice the volume of the original cube (so in this case, the new cube should have volume 2, and its sides should have length 2^(1/3). But 2^(1/3) is a root of the irreducible rational polynomial x^3 -2, so it has degree 3, and again, 3 is not a power of 2.

What's remarkable about this is that, once you prove the theorem (which isn't that hard, just a little fussy), you can dispose of those three old contruction problems so easily.

(Anyone who wants more details - I've left out a lot - can consult any book on Galois theory. Also, Nathan Jacobson's "Basic Algebra I" covers this [https://store.doverpublications.com/0486471896.html] --- it's a classic of abstract algebra which I like a lot, though a little old-fashioned.)

A long time ago, I spent the summer at my university where I was a mathematics major. I needed a job to pay for groceries, so I took a part time copy editing job at the math journal.

We got at least one "whack job" paper a week. Bear in mind this was when the internet was first getting traction, so I knew some of these guys from usenet…

> In fact, members of the academy were so tired of being inundated with quackery that in 1775 they passed a resolution not to accept solutions to the problems of circle squaring, angle trisection, or cube doubling.

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.

A "crank" is a very specific type of person, who will not heed any constructive criticism and in fact deliberately avoids resources from the establishment. Any dismissal is viewed as a conspiracy by the establishment to keep their brilliant ideas from dismantling the establishment's sacred cows.

Like concern trolls, their goal is seemingly to waste the time and energy of anyone willing to listen or engage, except they're not doing it wittingly, so you just wind up feeling like a jerk when you inevitably have to ignore their latest 20-page ramble and get some real work done.

Thank you for a comment coming from a position of genuine compassion for people who may not have had many opportunities in their life to train their minds.

The description of cranks as old, retired males with a minimal mathematical background given by U. Dudley seems to agree with what you say, btw.

As they say, sounds good, doesn't work. You can tell the genuinely curious sort from true cranks at a glance, and this article is about the latter. Every academic has interacted with far too many true cranks.

I always try to give rebuttals that are accessible, explaining in plain English what is going wrong and giving resources for follow-up learning. It doesn't work -- you get "that's cute, you still believe in textbooks, when I've proven them all wrong."

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 "censorship".

I think the best way of dealing with nonsense in Internet forums is to give a single reply, and then go away. Getting dragged into an ongoing "discussion" is unlikely to be worth the effort, since such people typically resort to rejecting evidence and making ad hominem attacks.

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.

I completely agree. But might some fraction of such people be “won over” by methods other than logic? Asking them how they got interested, perhaps, and drawing out what in their past caused them to become so obsessed?

Or even by redefining the goal of the debate?

It may be that I’m giving too much credit and most are truly hopeless. But so often with “people problems” I’ve seen approaches work beautifully and which in retrospect seem obvious. But in the moment I would never have thought up because I was considering things so narrowly.

In my experience, most of these people are over twice my age and slip into condescension the second I stop laying down logical arguments. If I don't argue against them logically, they invariably walk away triumphant, thinking they've just educated some ignorant young man. It makes the problem worse, so I might as well not talk with them at all.

In any case, their stories are all remarkably similar...

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

I agree with the main argument but would like to note "crank" in not an all or nothing description. Sometimes the problem as publicized doesn't exactly match the precise problem. For example you can trisect an arbitrary angle if allowed an infinite number of steps. Sometimes the problem is in breaking the abstraction layer. For example one of my kids thought you could make arbitrarily slow motion videos by taking slow motion videos of slow motion videos. And that brings up the issue of how to handle a crank. I loved that my son thought through the video issue and didn't want to inhibit future thinking. We ran some experiments taking video of the tv and it was fun. Sometimes people won't accept counter arguments and evidence (sometimes that person is me) and there's a time to move on. Still, in my experience few people are true die hard cranks and most people respond well if given the right direction.

> 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 a breakthrough

Thats when you say sure well start a basic research lab that will be $100 mil per year

Well, MOSH breaks through the speed of light latency limitation of SSH by ... predicting the server's response.

Although the laws of physics can't be broken, in certain scenarios we can simulate we have done just that. And often that's just what you need to get ahead of your competition.

You sound just like a VC!

"You're saying we can't do HFT between Tokyo and New York faster than the speed of light? Here's a completely unrelated product, that does something completely different, and the limit they're working with doesn't really apply to us. So it is possible! Maybe you should go to Burning Man, that would open your mind.."

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.

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.

I encountered something similar almost a decade ago on this forum when discussing the halting problem: https://news.ycombinator.com/item?id=1322901

There's a flipside of this, where people incorrectly lord "mathematical impossibility" over others as a way to shut down discussion. You see this on the topic of cryptographic backdoors especially. I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position.

The interface between plain language and math is messy. I don't think I've ever seen something suggested that was actually mathematically impossible. Even the halting problem is easily solved in practice.

This is where a very carefully worded description of the problem may be required.

Cryptographic backdoors are possible (See Clipper and LEAF for previous examples). Cryptographic backdoors that will only ever be used "legitimately" aren't, and legitimacy isn't a mathematical concept.

>Even the halting problem is easily solved in practice.

no, it's not. Knowing that this specific program halts or not doesn't address the issue.

> Even the halting problem is easily solved in practice.

You don't grok what the halting problem is. What you're describing (I assume) is determining if a specific program is going to terminate. That's not the same problem.

From Wikipedia:

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

The entire field of static analysis is "solving" undecidable problems effectively and productively all the time. Just accept a few false positives or false negatives and suddenly the field opens up to be amazingly useful.

Yes it isn't literally solving the halting problem. But I've had a weird number of people tell me that the stuff I work on doesn't work because of things they learned in undergrad.

I "grok" very well what the halting problem is, thank you. It's colloquially used in the sense of being unable to tell whether a program terminates. For reference I direct you to early static analysis tool promo materials (ex. Coverity) which usually explicitly address the "doesn't this run into the halting problem?" question given its common occurrence.

> I'm against cryptographic backdoors, but claiming they're not technically possible is a losing position.

I never seen anyone serious ever claim that cryptographic backdoors are impossible.

> Even the halting problem is easily solved in practice.

Like, how exactly?

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

realisticstandpoint, 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.

In a company I worked for, systems were brought to their knees because of a while loop that went infinite under poorly tested conditions. There was a meeting and the head of the dev team came down to tell us that, in the meeting, it was decided that we should not use iteration any more because it runs the risk of going infinite. Instead, we should use recursion for all our looping needs.

That was in a C# shop so of course the "decision" was never implemented. My guess is that this was a completely mad decision taken by non-technical managers in a moment of panic, who had pressed our tech lead a bit too much on why software breaks and what can be done to avoid it breaking- and then latched on to some off-hand comment about recursion being an alternative to iteration, and ran with it.

Their head probably would have exploded when they saw what the C# compiler did with tail recursive functions . :-D

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.

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 calls do terminate.

But, actually, the most straightforward way to show that most 'everyday' programs terminate is -- assuming functionality of the language runtime as stated -- that they typically consist of non-recursive functions or functions on structurally smaller inputs. It would be obnoxious, but not difficult to show that a program like 'grep' terminates, assuming functionality of the operating system and hardware on which its running. This is actually fairly straightforwards, and many many functional languages with a focus on correctness have totality checking builtin. For example, Idris and Agda.

Of course, if you're going to ask to prove both functionality of the operating system (like Linux + glibc) or the processor itself, then that could indeed be trickier. But, if you limit your stack, it's certainly possible. The truth is that most computing does not consist of solving Turing complete problems.

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

This comment is not germane to the point you were making, just wanted to share:

I am a web dev who knows nothing of the Collatz conjecture, so I had to check out the Wikipedia article for it. Thanks for teaching me something today.

I wrote this JavaScript function based on what I read in the article. It's a simple algorithm but it was fun to see it work. For anyone who is in my shoes (weak mathematical background), running this function might be a useful supplement for illustrating the gist concept of the Collatz conjecture:

Sure, you can do that with formal methods, but proving that a program is correct or that it halts is not the same as solving the halting problem.

That's not what the OP means, from what I can tell, but in the real world even a program like "while true {}" can be guaranteed to halt because eventually someone will figure out it's stuck in an infinite loop and abort it.

(tongue in cheek, of course, but I think the OP is trying to capture a similar pragmatic view of the halting problem)

http://norvig.com/beal.html

Peter told me he often gets candidate solutions that the sender hasn't even validated.

If you can put the points of the compass against the straightedge, which gives you a marked straightedge, you can trisect an angle. But that's considered cheating. Archimedes is credited with figuring out this approach.

I used to answer correspondence for the EFF Cooperative Computing Awards (which are an actual financial prize for finding very large primes) and people who wrote in were almost uniformly either kids or people meeting all of the criteria mentioned here.

Almost none of them thought it was important to understand any prior results about primality testing before submitting a claim for the prize, while a majority didn't seem comfortable with the idea of a mathematical proof or theorem. In general, they didn't have a sense that some properties are always true, some are never true, and some are sometimes true and sometimes not true, and that mathematical reasoning can often definitively establish which of these categories a particular property is in.

"Beware of Cranks" shows a terrible understanding of how major progress in science and technology happens. If you go around flipping the "crank bit", sure, you will save yourself spending time evaluating lots of correct negatives and have more time to make on incremental progress, but you will also have a couple of false negatives, one or two of which will go on to change the world. World change is dominated by black swans.

Conversely, Thiel's Hereticon conference idea is brilliant and shows a terrific understanding of how progress in science happens.

I wonder if Andrew Wiles had taken a different approach when announcing he had solved Fermat's Last Theorem if he would have been considered a crank. I would imagine that problem would have attracted nonsense solutions prior.

That's a big hypothetical, though. Andrew Wiles had been producing sensible mathematics in the community already, so there was no reason to suspect him of being a crank. Also, his proof did not emerge in a vacuum, he pursued approaches that were already known to be connected to FLT.

As for FLT attracting nonsense solutions: Yes, plenty of them. It being such a simply stated problem, and immediately understandable to laypeople certainly exacerbated the problem.

Fair point I have no familiarity with his earlier work, or even that there was suspicion of a connection, I did mean for my point to be a bit more general, just seemed like a reasonable example

A previous discussion of Underwood Dudley's classic article: https://news.ycombinator.com/item?id=14446708

Super curious---I actually never took trig (complicated story), so I don't understand the trisecting an angle thing at all. What is it that makes measuring the angle and then dividing that measurement by 3 impossible?

"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.

While dividing by three is easy, dividing an angle by three with just a compass and a straight edge is impossible. Numberphile[1] did a video on this a few years ago

[1] https://www.youtube.com/watch?v=6Lm9EHhbJAY (Euclid's Big Problem - Numberphile)

Tangential, but interesting: while it's impossible with a compass and ruler, one CAN trisect an angle with origami.

https://plus.maths.org/content/trisecting-angle-origami

It's not the actual measurement, it's the physical act of dividing an angle graphically into thirds using nothing but a compass and a ruler.

An important aspect of this isn't that you cant trisect any particular angle, its that you cant trisect any arbitrary angle, plenty of angles, like 90 degrees, are trivial to trisect.

Yes. The better way to phrase it would be that some angles are impossible to construct, and importantly that includes a trisection of some angles that can in fact be constructed.

Interesting. So like you have rational numbers and irrational numbers, you have trisectable angles and non-trisectable ones.

This analogy is rather precise—see this comment elsewhere in this thread.

https://news.ycombinator.com/item?id=21209466

The "compass" and "straightedge" are (nowadays) just a colorful/concrete way to describe the problem. When mathematicians consider this, they phrase the conditions in such a way that no physical "compasses" or "straightedges" are involved.

For example, you might say: (1) If you have 4 different points P, Q, R, S so that the lines PQ and RS are not parallel, you may "acquire" their point of intersection; (2) If you have 4 different points P, Q, R, S and the circle with center P and radius PQ intersects the line RS then you may "acquire" the point(s) of intersection of the circle and the line; (3) If you have 4 different point P, Q, R, S and the circle with center P and radius PQ intersects the circle with center R and radius RS, you can "acquire" the intersection point(s) of the circles. ("Acquire" a point means roughly that your number system now contains the coordinates of the point.)

Notice that this removes the problem of people doing unintended tricks with or drawing horribly complicated diagrams with physical compasses or straightedges, and makes mathematically precise what is allowed.

The following is probably more than you want to know, even though I'll omit lots of the details. The idea is that circles are defined by quadratic equations, and lines by linear equations. At every step, you're solving (acquring the roots of) simultaneous linear or quadratic equations. Starting with the rational numbers, as you "acquire" new points, you "extend" the rationals to bigger

fields"by extensions of degree 1 or 2". Since degrees multiply, at any point, you've "extended" the rationals by a total degree 2^n.So the result is: Theorem. Any point you construct must (a) lie in an extension of the rationals of degree 2^n; (b) be

algebraic, in the sense that its coordinates are roots of rational polynomials.Now take something like trisecting a 60 degree angle. A third of 60 is 20, and to construct a 20 degree angle you need to construct t = cos 20 degrees. But from trig, t is a root of x^3 - 3 x - 1 (which is

irreducibleover the rationals), so t has degree 3 --- and 3 is not a power of 2. Hence, a 60 degree angle can't be trisected.Squaring the circle means given a circle, construct (the side of) a square with the same area. Take the circle to have radius 1, so its area is pi. The square you need would have side pi^(1/2), but pi (and pi^(1/2)) isn't

algebraicin the sense noted above. (Lindemann showed pi is transcendental.) So you can't square an arbitrary circle.Duplicating the cube means given a cube (say with sides of length 1), construct (the side of) a cube whose volume is twice the volume of the original cube (so in this case, the new cube should have volume 2, and its sides should have length 2^(1/3). But 2^(1/3) is a root of the

irreduciblerational polynomial x^3 -2, so it has degree 3, and again, 3 is not a power of 2.What's remarkable about this is that, once you prove the theorem (which isn't that hard, just a little fussy), you can dispose of those three old contruction problems so easily.

(Anyone who wants more details - I've left out a lot - can consult any book on Galois theory. Also, Nathan Jacobson's "Basic Algebra I" covers this [https://store.doverpublications.com/0486471896.html] --- it's a classic of abstract algebra which I like a lot, though a little old-fashioned.)

* (a) lie in an extension of the rationals of degree 2^n; (b) be algebraic, in the sense that its coordinates are roots of rational polynomials.*

(a) implies (b) here, but I’m sure you know this.

From myself, I recommend Aluffi’s “Algebra. Chapter 0”, it’s more modern and I find its style much more matching my taste.

See also this site on weekends, when every "physics revolution" and "fix" for dark matter in cosmology gets posted.about.

A rare genuinely obligatory xkcd: https://xkcd.com/1758

A long time ago, I spent the summer at my university where I was a mathematics major. I needed a job to pay for groceries, so I took a part time copy editing job at the math journal.

We got at least one "whack job" paper a week. Bear in mind this was when the internet was first getting traction, so I knew some of these guys from usenet…

lol

>

In fact, members of the academy were so tired of being inundated with quackery that in 1775 they passed a resolution not to accept solutions to the problems of circle squaring, angle trisection, or cube doubling.This is hilarious.