| ▲ | graycat 6 days ago |
| Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b). |
|
| ▲ | tgv 6 days ago | parent | next [-] |
| Nobody is talking about a finite state machine in complexity. Its time complexity is n, and its space complexity is 0. The Halting Problem specifically pertains to Turing Machines. |
| |
| ▲ | graycat 5 days ago | parent [-] | | What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it. The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote. And I did not claim that what I wrote is a contribution to "complexity theory". The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment. | | |
| ▲ | tgv 5 days ago | parent [-] | | > What I wrote is correct What your wrote is pretty much trivial, and not related to the topic of the article. It's also not practical, since the space needed to represent even a small program as an FSM is very large. Just try to write an FSM that reads binary coded 16 bit numbers, and has to find the maximum value. Now imagine sorting just 100 of them. | | |
| ▲ | graycat 5 days ago | parent [-] | | > What your wrote is ... not related to the topic of the article. The article was: The Halting Problem is a terrible example of NP-Harder and I wrote: > So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". > "Trivial"? I never claimed the post was a significant contribution to computer science or complexity theory, and at most only a tiny fraction of posts at HN are such. Also, my post does not address the complexity theory question of P = NP. If what I wrote was "new, correct, and significant", then I should have sent it to a good computer science journal. I've published enough papers in good math and computer science journals to notice that the checks take a long time to arrive. I'm not in academics and never wanted to be. HN is not a journal of new, correct, and significant work in computer science. From responses in this thread, the post has proven to be at least curious and interesting to some of the HN audience. |
|
|
|
|
| ▲ | brap 6 days ago | parent | prev | next [-] |
| But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s always decidable. |
| |
| ▲ | JohnKemeny 6 days ago | parent [-] | | No, the halting problem doesn't hold when you have finite memory (as per OP's point). As OP says, after finitely many iterations (at most 2^n many), you have to be back at a previously seen state, and can terminate. | | |
| ▲ | chriswarbo 6 days ago | parent | next [-] | | Architectures like x86 can only address a finite amount of RAM, since they have a fixed word size (e.g. 64 bits). However, their memory is still unlimited, since they can read and write to arbitrary IO devices (HDDs, SSDs, S3, etc.); though those operations aren't constant time, they're O(sqrt(n)), since they require more and more layers of indirection (e.g. using an SSD to store the S3 URL of the address of ....) | |
| ▲ | tromp 6 days ago | parent | prev | next [-] | | The halting problem requires both 1) unlimited length of programs whose halting behaviour is to be decided (so it can not be limited to program of at most 10 petabytes) 2) for those programs to have unlimited memory available You're arguing about point 2) in response to a post about point 1). | | |
| ▲ | JohnKemeny 6 days ago | parent [-] | | Well, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point. |
| |
| ▲ | 6 days ago | parent | prev | next [-] | | [deleted] | |
| ▲ | 5 days ago | parent | prev [-] | | [deleted] |
|
|
|
| ▲ | Tainnor 6 days ago | parent | prev | next [-] |
| This approach suffers from two major problems: * It makes computability and complexity dependent on individual machines (now a program may halt on machine A, but not on machine B). For various reasons, we don't want that. * The entire state space of a single machine consists of all the registers, memory cells, etc. But keeping track of all states that have been visited before requires exponentially more space than the space that is actually available on the machine (because you're computing the powerset). So the machine itself can't solve its halting problem, only a much more powerful one can. Very often, impossibility results in infinitary mathematics translate back to "there's no reasonable way to do this" in actual practice where things are finite. |
| |
| ▲ | Ukv 6 days ago | parent [-] | | You wouldn't necessarily need to keep track of all states that have been visited before, to my understanding, just one extra state that you move along at half the speed (so it'll eventually also enter the loop, and then the state you're progressing at full speed will loop around and hit it). So 2X the memory and 1.5X the time/compute of the program on its own. | | |
| ▲ | Tainnor 6 days ago | parent | next [-] | | This is interesting and I wasn't aware of this algorithm, thanks. I still maintain that it's practically infeasible to exhaust the entire state space of any modern machine. | | |
| ▲ | Ukv 6 days ago | parent [-] | | True, but practically I don't think you'd ever need to - should be able to narrow things down with insights/heuristics (and even with the simple algorithm alone, most programs would loop or halt far sooner). Often seems to be presented as if humans can make some deductions or introspections that machines/AI would be incapable of seeing, or that the machine would have to rely on brute force for, but I don't think there's actually any result to that effect. |
| |
| ▲ | TheDong 6 days ago | parent | prev [-] | | Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total number of states. Say you have a machine with 128 bits of state, if it halts in 2^128 (roughly 340 undecillion) steps, that means it halts. If it's still going after 2^128 steps, then it'll keep going forever. So, to see if a 128 bit machine halts, you only need an extra 128 bits to count up 1-by-1 to 2^128. Sure, you also need a few thousand times the lifetime of the known universe just to count that high, but you know, It's O(2^128) instructions which means it's O(1). Good luck doing that on any machine with any real amount of memory of course. Really easy to write "just count to 2^128", but not so easy to do it. |
|
|
|
| ▲ | jerf 5 days ago | parent | prev | next [-] |
| That's great and all, but nobody is talking about physical computers here. Moreover, it's a useless observation in practice as well because the full exponentially-large state space necessary to represent such systems is not a useful formalism to approach computers with for any purpose, be it brutally practical or entirely theoretical. See https://news.ycombinator.com/item?id=23431703 for some previous comments I made on this, and some rough numbers base on computers that were already small 5 years ago and seem even smaller today. It is not useful to say "hey, that thing you're using has a finite state space and that finite state space is only 10^2,585,827,973 large!" It's not like you're going to run out. |
|
| ▲ | userbinator 6 days ago | parent | prev | next [-] |
| More information on the algorithm to do so: https://en.wikipedia.org/wiki/Cycle_detection |
|
| ▲ | Sankozi 6 days ago | parent | prev [-] |
| Yes, lots of these problems assume fantasy infinite world. Big O notation also suffers from this - it's almost useless for real world problems. |
| |
| ▲ | virgilp 6 days ago | parent | next [-] | | > Big O notation also suffers from this - it's almost useless for real world problems. This is quite a bold claim. Yeah "in the real world" you often need to take into consideration the constant factors... but to go this far to say that Big O is useless? It's very useful to figure out what would likely work (or not) for your problem, given that you know the data size - I used it for exactly that, many many times. | | |
| ▲ | Sankozi 6 days ago | parent [-] | | Let's say you have 2 algorithms. Constant time O(1) and exp time 2^n. It seems constant time is better. But in fact it runs always 42 years. While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe. Big O says how fast complexity grows, but it doesn't say what that complexity exactly is. Does something like that happens in real world? Yes, but of course not in such drastic ways. | | |
| ▲ | forrestthewoods 6 days ago | parent | next [-] | | The fact that Big O notation is sometimes misleading or not helpful is not evidence that it is not generally useful. https://www.tumblr.com/accidentallyquadratic | | |
| ▲ | qludes 6 days ago | parent [-] | | As a concept it is pretty useful for me in a handwavy astrophysics math way because I otherwise wouldn't necessarily know how to make my naive solution fit real world constraints. |
| |
| ▲ | jhanschoo 6 days ago | parent | prev | next [-] | | If you are writing everyday programs your constant factors are going to be very comparable and proportional to the size of your program, unless you have somewhere in your program hardcoded numerical constants like, run this loop 1 trillion times. | |
| ▲ | hnfong 5 days ago | parent | prev | next [-] | | If we're talking about "fantasy world" vs "real world", the "always run 42 years algorithm" surely is closer to fantasy world than most reasonable Big-O analyses... If you need to pull an example from fantasy world to illustrate your point about Big-O notation not being useful "in the real world" you're probably committing the same alleged mistakes as computational theorists... | |
| ▲ | virgilp 5 days ago | parent | prev | next [-] | | > While exp one starts to run longer than millisecond for sizes bigger than number of particles in universe. You don't really know how this works, do you? I can guarantee that thera are more than 1M particles in the universe. And if you iterate 2^1M times, doing nothing, on a current computer... that's basically indistinguishable from an infinite loop. | |
| ▲ | qazxcvbnm 6 days ago | parent | prev | next [-] | | A very exaggerated example to use exp time… Whatever your constant, for exp time, it’s going to run for times longer than the life of the universe on probably any n > 10… Since you know, log time is practically constant | |
| ▲ | pyfon 6 days ago | parent | prev [-] | | Most of the time the constants are going to be similar. And by similar I mean < 3 orders of magnitude say. So 2^9 or adding 9 to N eats that up pretty quick. |
|
| |
| ▲ | MattPalmer1086 6 days ago | parent | prev | next [-] | | You find Big O notation useless for real world problems? I find it useful to characterise algorithmic performance, e.g. O(1), O(n) O(n^2), etc. What do you find useless about it - and do you know of something that works better? | | |
| ▲ | MrBuddyCasino 6 days ago | parent | next [-] | | Simpler algorithms are usually faster for small N, and N is usually small. Big O assumption is fantasy world where N is always large, and constant factors that slow down an algorithm can be ignored. | | |
| ▲ | nottorp 6 days ago | parent | next [-] | | https://news.ycombinator.com/item?id=26296339 Small N right? | | | |
| ▲ | MattPalmer1086 6 days ago | parent | prev | next [-] | | Yeah, constant factors are not represented and often make a big real world difference. Good point. | |
| ▲ | coldtea 6 days ago | parent | prev [-] | | >Simpler algorithms are usually faster for small N, and N is usually small. This mentality is how we ended up with cpu and memory hogging Electron apps... | | |
| ▲ | JohnKemeny 6 days ago | parent | next [-] | | That's not an accurate description. For example, it is common in sorting algorithms to do an n² algorithm like bubble sort when the list to sort is small (e.g. <50), whereas when it's larger, we do an n log n algorithm like merge sort. The issue is that merge sort does recursion, which comes with some extra cost, so that an n² algorithm beats an n log n algorithm, provided n is small. It has nothing with your criticism to do. | | |
| ▲ | Al-Khwarizmi 5 days ago | parent [-] | | You can (and probably should) add a threshold to recursive algorithms like mergesort so that they don't end up doing recursive calls on very small arrays. For arrays smaller than the threshold, insertion is faster than bubble sort. And if you really don't want recursion for large arrays to begin with, you have heapsort or Shell sort. I don't think there is any practical case where using bubble sort makes sense, except "efficiency doesn't matter for my use case and this is the code I already have". | | |
| ▲ | graycat 5 days ago | parent [-] | | As in one of volumes of Knuth's The Art of Computing, Heap sort is in place and achieves the Gleason bound so can be regarded as not beaten by quick sort. |
|
| |
| ▲ | MrBuddyCasino 6 days ago | parent | prev [-] | | Electron a) isn’t really slow for what it does b) introduces many layers of abstraction, leading to larger memory consumption compared to „native“ apps c) is certainly not algorithmically unoptimized, it runs on a software stack that has been tuned like few others using billions of dollars You just loosely associated words and concepts that occupy a similar emotional niche. |
|
| |
| ▲ | Sankozi 6 days ago | parent | prev [-] | | Better - estimate complexity so things like "this algorithm will take 1234 + 2n + 500m operations " for our use case Much better - research (not always possible) Best - benchmark it using realistic data from your use case | | |
| ▲ | bawolff 6 days ago | parent [-] | | > Better - estimate complexity so things like "this algorithm will take 1234 + 2n + 500m operations " for our use case I feel like that is never the level of detail you want. Either that is way too much detail and big-oh notation abstracts away the meaningless stuff. Or, if this level of detail matters, then you really need to go much further. Think about cache hit ratios, memory layout issues, different speed of different operations, etc. Calculating number of operations is a weird middle ground that seems pretty useless. |
|
| |
| ▲ | suddenlybananas 6 days ago | parent | prev | next [-] | | >Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort. | | |
| ▲ | Sankozi 6 days ago | parent | next [-] | | Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms. | | |
| ▲ | suddenlybananas 6 days ago | parent [-] | | >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale. |
| |
| ▲ | LegionMammal978 5 days ago | parent | prev [-] | | Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb. | | |
| ▲ | Al-Khwarizmi 5 days ago | parent [-] | | Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there. |
|
| |
| ▲ | nottorp 6 days ago | parent | prev | next [-] | | Please read accidentally quadratic from time to time... | |
| ▲ | mkleczek 5 days ago | parent | prev [-] | | Which is evidenced everyday when optimizing database performance by creating indexes /s |
|
