This is a rant I’ve had in my head forever, so thanks for posting this. A lot of people use the proof that the halting problem is undesirable to make some deep philosophical point, like this one. But the actual proof is so disappointing and non-philosophical that I wonder if anyone making these grand statements has ever read it. It just invents a program which outwits the halting detector by doing the opposite of what it would otherwise say.
Its like, if you met the smartest person in the world, and you asked them “will you answer no to this question” and then no matter what they said you laughed in their face and said hah, guess you’re not so smart, are you?
And THAT is why you think we don’t live in heaven?
Like, OP says that because of this proof we can’t run HALT() on a program that assets the Goldbach conjecture. What? That’s entirely orthogonal from the proof of the undecidability of the halting program, unless one of the primes has embedded a trick logic question into itself somehow. There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”. There you go, you’re back in heaven again!
> There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”.
Doesn't work that way. If we have "HALT_FOR_...EXCEPT_THAT_ONE_TRICK_PROGRAM", then we can simply create "HALT_FOR_ACTUALLY_EVERY_PROGRAM" by:
if (is this that one trick program?) then
return THE CORRECT ANSWER FOR THAT TRICK QUESTION, HARD-CODED
else
answer = HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM()
return answer
...but this is impossible, because then it would actually solve the full halting program, and we know it's impossible.
So the best you can have is "Solve the halting problem for a bunch of programs, but not for a bunch of others, but that's okay because will call the latter as 'trick programs.'"
And the problem is that you can't give a mathematically satisfying definition of what is a trick program, and whatever you try, you'll likely end up defining a lot of actually interesting programs as trick programs. So it's actually "Solve the halting problem for some programs, but not others." And that's not terribly interesting, because we already know it's possible.
> So the best you can have is "Solve the halting problem for a bunch of programs, but not for a bunch of others, but that's okay because will call the latter as 'trick programs.'"
The awesome and surprising thing is, I’ve actually written such a program! It regularly runs the program to test, but stops and screams “trick program!” if the program to test did not finish within five minutes. Sadly, I haven’t been awarded my Fields Medal yet, probably because I didn’t use LLMs.
I am probably not the only one who finds the above as pointless as trying to determine whether the sentence "this sentence is false" is true or false. It is neither, but most of the time we're interested in problems that have answers, and that problem space turns out to be huge and extremely useful.
What are some good examples of practical programs that aren't trying to create a chain of computation that is ultimately circular and self-referential yet still run into trouble with the halting problem?
> What are some good examples of practical programs that aren't trying to create a chain of computation that is ultimately circular and self-referential yet still run into trouble with the halting problem?
Almost any unproven mathematical conjecture, e.g. a program that searches for counterexamples to the Riemann hypothesis. More practically, a lot of problems reduce to SAT, so these days quite a lot of systems work by just running a SAT solver on the problem (e.g. dependency resolution in some build systems), and it's fast most of the time but you can never be sure it's not going to get stuck.
> Almost any unproven mathematical conjecture, e.g. a program that searches for counterexamples to the Riemann hypothesis.
This is a very good example. We don't know whether such programs will ever stop, and knowing is exactly equivalent to resolving the conjectures.
> More practically, a lot of problems reduce to SAT, so these days quite a lot of systems work by just running a SAT solver on the problem (e.g. dependency resolution in some build systems), and it's fast most of the time but you can never be sure it's not going to get stuck.
This is a less good example because SAT solvers can always run in finite time and can be proven to halt. Even if they do "get stuck", they will take exponential time rather than infinite time.
There are probably some problems that arise practically that are undecidable in general (e.g. type checking for sufficiently expressive type systems), but problems that "reduce to SAT" are never examples of such undecidable problems because SAT is decidable.
I was going to say the same thing about SAT, or any NP-hard problem.
The first example doesn't seem to be good either however. I don't think that proving a mathematical conjecture which has resisted proof for decades (or longer) is something that we would typically expect a computer program to be able to do. Whenever this happens, it is hailed as a major breakthrough.
The point is that it can complicate analysis of a program, at least if you take the fundamentalist view that all program behaviour should be provably correct. Like if you need the collantz sequence of a number or something in your program, you would just calculate it and use it, but it's surprisingly hard to prove that it always exists. Which isn't so much a problem in itself as it complicates trying to prove anything else about your program's behaviour.
The philosophical issue is there are questions which seem "simple" and have answers, but even if given the answer you could not know whether it was the right answer.
Kolmogorov complexity is undecidable because the halting problem is undecidable. If we could solve Kolmogorov complexity we could do Solomonoff induction and build AIXI and solve (at least one formulation of) decision theory.
The real problem (imo) is that proof search is also undecidable (either directly from halting problem or similar argument) and so there isn't a procedure we can write that identifies trick programs to exclude as special cases. There are an infinite number of various trick programs for which halting is undecidable and recognizing them is undecidable.
The halting problem is more than that. While the proof constructs a relatively trivial Turing machine that basically puts the toddler's "Nuh-uh!" on solid mathematical ground, that's just the proof that there exists at least one Turing machine for a given halting oracle that can not be predicted by that halting oracle.
It is true that the halting problem itself is perhaps not directly what people seem to think it is, but people turn out to be right anyhow, because Rice's Theorem can be largely summed up as "It can be proven that we can not have nice things", if you'll allow me a bit of mathematician-style humor, which corresponds more-or-less to the way people talk about the Halting Problem.
This also explains why the Goldbach conjecture is in fact directly related to the halting problem and not orthogonal at all. Through Rice's theorem we can extend the halting problem quite easily to the solution to that and a lot of other problems.
By computer science standards, Rice's theorem is relatively basic stuff. I don't recall if the sophomore-level class I learned about this stuff did a full proof of Rice's theorem but I certainly recall several homework problems around applying the idea of the theorem to several specific problems by proving reductions of those problems to the halting problem. I also recall they really weren't particularly difficult problems. It's not hard to reduce that sort of interesting question to the halting problem. Low-level undergrad stuff, stuff down in the very basics of computer science qua computer science suitable for making up several problems in the weekly homework assignment for the intro to (real) computer science course, not complicated abtruse stuff that can't be applied by anyone less than a doctoral candidate with a few months to burn. All sorts of problems are reducible like this.
And that is why the "halting problem" in fact is the reason why we can't have certain nice things we'd really like. For example, the mentioned ability to prove that two functions really are equivalent would have practical utility in a wide variety of places (assuming somewhat reasonable efficiency), like compiler optimizations.
Your intuition is correct in one respect though; there is a sense in which it isn't really "The Halting Problem (TM)". You could take a wide variety of other problems and call them "the" fundamental problem, and reduce the halting problem to those problems. The Halting Problem just turns out to be a particularly concise specific expression of the general problem that is easy to express for Turing Machines. It just makes for nicer proofs than the alternatives. "The" core problem could arguably be something more like Rice's Theorem proved on its own as a fundamental proof without reference to the halting problem. You could call the Halting Problem a historical accident that we hold on to due to a path dependency in how math happened to develop in our history. An alien race might have a reasonably different view on the "fundamental problem", but then they'd have a something fairly similar to Rice's Theorem sitting on top of it that we'd all recognize.
Yeah, it's fundamentally a "if god can create anything, can he create a rock that he himself cannot lift?" kind of deal - a meaningless philosophical debate because the parameters were constructed to make the problem possible in the first place. An "intellectual trap", if you will.
Alternatively: We know that the earth is not perfectly flat, so why are our spherical cows not rolling off the meadow?
function HALT(program, input):
# This is a "magic" function for our proof - we assume it exists for all programs
# In reality, this function cannot exist because of the paradox we're about to create
# Returns True if `program(input)` halts, False if it runs forever
...
# Program D: Creates the paradox
function D(self):
if HALT(D, self) == True:
loop_forever()
else:
halt()
How would performance be a concern for rendering the UI of a terminal app? Surely that happens in less than 0.001% of all cases. And of course no one in their right mind is implementing the core functionality of their app with react state variables. (Right..?)
Haven’t used this library, but the answer is the same as it is for real React apps. How does this application perform if I have a scrollable view with 50,000 items in it and I press the down arrow? This kind of thing is why React can be the cause of bad performance.
Any viewer of data that has 50,000 elements in it has this many items with a scroll wheel. It doesn't matter if it's on the screen at the same time, this is the kind of thing that the UI is supposed to be abstracting away from you; you just describe the UI and the renderer makes it appear on the screen. Example apps (not built with Ink, just some that fit into this category): less, https://fx.wtf, sqlite...
And this is why React apps end up with bad performance by default. Doesn't crop up in simple tests and light usage, but the bad scaling will catch up with you when you deploy to production.
You seem to be concerned over a non-issue: I'm pretty sure you're the only person in this entire discussion who misinterpreted the graph. Does that mean the people you're talking about are yourself? :P
I don't really agree with this. I go and hang out with my friends, and we don't all end up getting outraged about stuff. I go for a walk in the park and no one is shouting at me; I go to a restaurant and people are sitting around normally discussing whatever. If you start quoting outrage bait that you read online, people might look at you strangely.
My point is I don't think people seek out outrage. Social media's algorithms may not explicitly reward it as transparently as `if (post.outrage > 100) post.boost()`, but outrage isn't some default rule of interaction.
const passwordRules = [/[a-z]{1,}/, /[A-Z]{1,}/, /[0-9]{1,}/, /\W{1,}/];
async function createUser(user) {
const isUserValid = validateUserInput(user);
const isPasswordValid = user.password.length >= 8 && passwordRules.every((rule) => rule.test(user.password));
if (!isUserValid) {
throw new Error(ErrorCodes.USER_VALIDATION_FAILED);
}
if (!isPasswordValid) {
throw new Error(ErrorCodes.INVALID_PASSWORD);
}
const userExists = await userService.getUserByEmail(user.email);
if (userExists) {
throw new Error(ErrorCodes.USER_EXISTS);
}
user.password = await hashPassword(user.password);
return userService.create(user);
}
1. Don't use a bunch of tiny functions. This makes it harder for future eng to read the code because they have to keep jumping around the file(s) in order to understand control flow. It's much better to introduce a variable with a clear name.
2. Don't use the `a || throw()` structure. That is not idiomatic JS.
2a. Don't introduce `throwError()`. Again, not idiomatic JS.
3. Use an enum-like object for error codes for clarity.
4. If we must use passwordRules, at least extract it into a global constant. (I don't really like it though; it's a bit too clever. What if you want to enforce a password length minimum? Yes, you could hack a regex for that, but it would be hard to read. Much better would be a list of arrow functions, for instance `(password) => password.length > 8`.
My issue with this is that you're using exceptions for control flow. A user not being valid is expected (duplicate username). A password not matching a regex is also expected.
Then, in general (not seen here as there are no types), I like to use a lot of types in my code. The incoming user would be of type UnvalidatedUser, whereas the return type of this function would be StoredUser or something like that to distinguish the incoming user type with the outgoing. I like to attach semantics to a type, not to conditions: https://existentialtype.wordpress.com/2011/03/15/boolean-bli...
It's a good point, especially because different return types is well supported in TS.
I made the same in plpgsql recently and opted for returning an implicit union of UserSession | Error, by returning UserSession in the signature and raising errors in the function. The alternative was to return json where you'd have to look at the body of the function to figure out what it returns (when successful), as opposed to the signature.
I'm not sure if I'm striking the right balance. Yes, the signature is "self-documenting" - until you hit an error!
My issue with that is that absolutely NOTHING will ever convince me that returning error codes is a better idea than throwing exceptions. And that you seem to be using 'expected' in some weird cargo-culty sense of the word. An invalid user name is an error, not an expected case.
> An invalid user name is an error, not an expected case.
If you ain't expecting users to input bogus data, then you're putting way too much trust in said users.
Put simply: is it a bug in your own code if a user tries to use an invalid username? If yes, then throw an exception. If no, then return an error code. Exceptions represent programmer error; error codes represent user error.
> Exceptions represent programmer error; error codes represent user error.
No, they represent whatever suits the system design and the house style.
They're just tools to pass data and manipulate control flow.
If you become dogmatic and start insisting on what they must absolutely represent, you're only going to find yourself compromising design coherence and futily railing at colleagues when different representations are found to be appropriate.
With exceptions, it often makes sense to use them when failures inevitably just propogate up through a stack of nested calls or may appear anywhere in a sequence of calls. In these cases, return codes can grossly interfere with legibility and can lead to confusion when interim handlers squelch errors that really should have propogates up directly.
These are the kind of choices that are completely reasonable to make within a specific module (like an auth and accounts module), and you can always return to some other default policy at the interface of that module if your project/house-style needs such.
Engineering shouldn't feel so dogmatic as you suggest. It's a strong smell when it does.
“ Don't use a bunch of tiny functions. This makes it harder for future eng to read the code …”
This is where the naming things bit comes in. You name the function correctly, then when the body is read to understand that it works as named, you can remove that cognitive complexity from your brain and continue on. Once you’ve built trust in the codebase that things do what they claim, you can start getting a top-down view of what the code does.
I don't know. I really don't see any clarity improvements between, `user.password.length >= 8 && passwordRules.every((rule) => rule.test(user.password))` and `validatePassword(password)`. What if you want to add that the password must contain one special character? You don't actually know, by reading the name "validatePassword", if that work has already been done or not. You need to go read the function definition and check. And so even for such a small function, there is no name that you can choose to truly do what you claim and "remove the cognitive complexity from your brain".
Once a function gets to a certain threshold of size and reuse, I tend to agree with you. But I think that threshold is quite large - like at least 40-50 lines, or reused at least 3 times.
`validatePassword` is definitely clearer. When I'm getting familiar with a new codebase, I don't need to know how each thing happens, I need to know what happens. In fact, in your example, you've already abstracted testing against the rules. (AAMOF, the password length requirement should be another rule...)
Also with that example, that is about the limit I would tolerate in a conditional that decides the next step in this app. I just need to know "if the password is valid, go to $SCREEN; if not, turn on these messages." I don't care about a string of expressions, I care about what it's doing and I don't want to parse the code every time to figure out "oh, this is just password validation."
This is different from verifying that features are implemented - now I need to know the minutia.
It is definitely not clearer to me. I have no idea what happens in the `validatePassword` function. Does it make a synchronous network call that will stop the world for half a second? Does it throw an exception, or return an error object? I will also have to search the rest of the code to see who else calls it, and potentially refactor those callers as well.
Any smaller function broken out of a larger function is (slightly) confusing. I find that a genuinely large function is much more confusing than two functions half the size, but a petite little function less than 20 lines long is not confusing to begin with.
The business rules for passwords and usernames are separate. It's okay for them to be separate methods.
You also know that the 'valid password' function is going to list the rules for a valid password. If you get a task to change the password creation rules, do you honestly expect people other than you to remember that code is in the createUser function and not the valid password function??
I don't think you're being honest with yourself about this scenario. Or if you are, this is going to cause you a lot of trouble over time.
> If you get a task to change the password creation rules, do you honestly expect people other than you to remember that code is in the createUser function and not the valid password function??
I don't expect anyone to remember where the code is, regardless of which function it's in. I don't even expect them have been aware of every function to begin with.
How do you expect people will find the `isPasswordValid` function? Because I know from experience that the way I would find it would likely be by looking at the `createUser` function to see what it does. I might do a case-insensitive grep for the word password first, but even then I'd just have to go look at `createUser` anyway, otherwise I wouldn't know whether `isValidPassword` was dead code or referring to a different password.
Look at it. It's under 20 lines long and handles one thing, which is creating a user. You unit test it by passing a user with an invalid password. You might possibly decide to put the validation of user input into one function and avoid mocking userService, but I don't see a good justification for splitting password and other user fields into separate functions.
I accept that if there was more logic then you might want to split it out, but seriously, it's tiny. The single responsibility principle doesn't justify making your production code much more difficult to read just so the unit tests around it are marginally easier to write.
I used to feel that way, but over time I've come to realize that for the vast majority of code pulling stuff out so you have only one level of nesting and only one pass/fail decision makes it easier to understand years later. I'm sure the compiler inlines a lot of stuff I pulled out.
The exceptions to this are situations where you need to do a bunch of sequential steps and cases where you are looping on stuff in higher dimensions.
I have gotten to the point that I consider a comment about the code to be a sign of trouble. (Comments about what the code is interacting with are a different matter.)
Abstraction is way better, I don't really want to know how the password is validated unless I know I'm facing issues with validation (which proper logging tells you about before you even dive into the code).
I don't understand why some people prefer being swarmed with details. It's not that they want details, but that they just hate navigating files (layer 8 + tooling problem) or that they "need" to know the details because not knowing them haunts them at night somehow.
Also, not having that as a free function makes me think it's not tested at all (although there might be some integration test that hopefully catch all errors at once, but I'm sure they don't either)
My only nitpick is that the const isPasswordValid = ... should be just before its use (between the first two ifs).
Other than that, I prefer this approach (although I would inline the booleans in the ifs to avoid the one-use variables. But that's ok).
> Don't use a bunch of tiny functions
Exactly this. I only do that when the function is used in more than 10 places and it provides some extra clarity (like something as clamp(minVal,val,maxVal){return max(minVal,min(val,maxVal))} if your language doesn't already have it, of course).
I also apply that to variables though, everything that is only used once is inlined unless it really helps (when you create a variable, you need to remember it in case it is used afterwards, which for me is a hard task)
I don't think so, if it does it will now too. In fact with my suggestion the regex checks will not run if the user is not valid (as it is now it will always run)
This is one of my pet peeves. I had an engineer recently wrap Dapper up in a bunch of functions. Like, the whole point of dapper to me is that it gets out of your way and lets you write very simple, declarative SQL database interactions and mapping. When you start wrapping it up in a bunch of function calls, it becomes opaque.
I always prefer having loadBooks than “select * from books” everywhere. I prefer my code to be just the language version of how I would write an explanation if you ask me one specific question. Not for DRY, but for quick scanning and only diving into details when needed
Yep, I’d hire you, and not OOP. There was some really questionable code structuring in there and I always wince at abstraction for abstraction’s sake. It always becomes a hindrance when something goes wrong, which is exactly when you don’t want to have a hard time deciphering code.
> 1. Don't use a bunch of tiny functions. This makes it harder for future eng to read the code because they have to keep jumping around the file(s) in order to understand control flow. It's much better to introduce a variable with a clear name.
If you have nested functions, that's not a problem.
Btw, why do you use regular expressions for some rules, but not for others? Regular expressions are perfectly capable of expressing the length requirement.
Something about Javascript and Typescript is really ugly to my eyes. I think it is the large keywords at the beginning of every line. Makes it hard to parse and read. I find C++ style much better to read.
> It would turn into a smoking hole in the ground if it somehow caught worldwide attention.
This seems untrue? Of course I like HN, but from the perspective of a typical person, HN is an ugly, hard-to-use website with "news" that caters to a small fraction of the population and is likely quite uninteresting to the rest. I think this is why it manages to stay roughly the way that it is - that and extremely thorough and strict moderation to keep it that way.
I remember when I was a kid, the doctor thought that my blood pressure was too high. Of course, I was just anxious because I knew they were going to give me a shot. What kid wouldn't be?? He took it again after I got the shot and it went back down to normal.
Its like, if you met the smartest person in the world, and you asked them “will you answer no to this question” and then no matter what they said you laughed in their face and said hah, guess you’re not so smart, are you?
And THAT is why you think we don’t live in heaven?
Like, OP says that because of this proof we can’t run HALT() on a program that assets the Goldbach conjecture. What? That’s entirely orthogonal from the proof of the undecidability of the halting program, unless one of the primes has embedded a trick logic question into itself somehow. There’s nothing stopping there from being a “HALT_FOR_EVERY_PROGRAM_EVER_EXCEPT_THAT_ONE_TRICK_PROGRAM”. There you go, you’re back in heaven again!
reply