9 ms·
>9) Do not write infinite loops or recursive functions. did GPT-4 just solve the halting problem?
by doctoboggan 3y ago
>9) Do not write infinite loops or recursive functions.
did GPT-4 just solve the halting problem?
- geoelectric 3y agoSeems slightly easier for me to guarantee something I wrote halts. The halting problem is more about a process analyzing someone else's arbitrary code.
- narrator 3y agoIf the brain is like a computer, how do humans even solve the halting problem? Maybe it's because humans feel anxiety at the unproductive passing of time while computers will just do what they're doing forever.
- i2cmaster 3y agoHumans tend to communicate/write software in what are really sub languages. Often these sub languages are not recursive.
- IIAOPSW 3y agoNothing you think about consciously has higher thread priority than the stay-alive loop.
- ethanbond 3y agoThey don’t really. People have different thresholds for acceptable exploration costs and heuristics for approximating those costs (as well as the opportunity cost of alternative courses of action). IMO, in biological systems the explore vs exploit tradeoff is pretty analogous to the halting problem. There doesn’t seem to be an optimal general “solution” to it. Once an organism is very familiar with its environment it’ll approximate near-optimal trade offs, which would suggest it’s just using heuristics.
- School-Cotton 3y agoHumans can’t solve the halting problem any more than computers can. For example, it’s trivial to write a program that searches by brute force for a cycle that would disprove the Collatz conjecture, and halts if it finds one. No human knows whether that program will halt.
- jameshart 3y agoHumans can’t solve the halting problem. Write a program that, for a positive integer, runs the Collatz process on it (if even: halve it; if odd, multiply by three and add one; repeat). If the process results in a 1, move on to the next number and repeat. If the process produces a number it produced previously, halt. (Worried you’ll need unbounded state for this part? Use tortoise+hare, it’s fine). This program halts if and only if the Collatz conjecture is false. Now, the Collatz conjecture might not be unprovable. But for now no human can tell you whether or not that program halts.
- genewitch 3y agoWhen I read about collatz I wrote a C# program that short circuits the calculation like that, but my programming chops are not great and it could only handle 3000 digits of memory serves. It's somewhere on my GitHub page and I'm curious how many other people released similar code to speed things up. I ended up using it to compare single core performance on any windows machine, because the timestamped logging was deterministic. Rewrote it in python and still use it these days.
- pjerem 3y ago> If the brain is like a computer That’s a common misconception. The brain is not like a computer. The brain can’t store and execute programs.
- kaba0 3y agoThe halting problem is about computable functions. Every real thing can at most solve computable functions — so for all practical purposes, a brain is a computer that has all the same limits.
- shkkmo 3y ago> That’s a common misconception. The brain is not like a computer. The brain can’t store and execute programs. Can't it? The brain is absolutely capable of emulating a turing complete system such as running a program.
- pjerem 3y agoCan it ? I mean, sure you can reason about a portion of code on your screen but there is no way you could emulate anything without some visual support. There is no way your short term memory could store the program and the variables. The human brain can barely remember 5 to 10 words for several seconds and you have no control on your long term memory. So yes your brain can somehow emulate a computer if you give him a pen, a sheet of paper paper, time, and a lot of sugar. But that’s not because it’s functioning like a computer but rather because you learnt how a computer work.
- moffkalast 3y agoif(going_to_halt) dont();
- redox99 3y agoIt's trivial to avoid infinite loops by adding some exit condition in case it takes too long, which is probably what you want here. And obviously trivial to avoid recursion too.
- Too 3y agoAvoiding recursion isn’t always that trivial if there are intermediate functions between the first function is called again. More dynamic code with callback functions is another case making this difficult.
- bentcorner 3y agoEvery program halts because no computer can run forever
- travisjungroth 3y agoOne description of the halting problem is that there are not just two categories of programs (halts and doesn’t), but a third of “undecidable”. To limit yourself to the category of “halts” isn’t solving the halting problem.
- jrockway 3y agoeBPF is a real-world system that also refuses to accept programs that might not halt. You don't have to solve the halting problem, you just have to deny the programmer loops (and loop-alikes, of course; recursive functions, jmp, etc).
- dragontamer 3y agoIIRC, some language model proved that one-layer of loops can be proven to halt vs not-halt. As soon as you add a 2nd layer of loops however, you reach Turing-completeness and suddenly the halting problem becomes unsolvable. ------- So you don't need to deny jmp/loops. You just need to deny _nested_ loops. And... find that old paper I read like 15 years ago to figure out the details to discriminate halt/not-halt in the single-layer loop language.
- napsterbr 3y agoYou could ask ChatGPT to find the paper for you! It told me the name of an old videogame I was trying to remember for years.
- jakear 3y agoThis is most assuredly false: while (state !== STOP): read = TAPE[index] [state, write, dir] = TABLE[read, state] TAPE[index] = write index = index + dir
- deleted 3y ago[deleted]
- vidarh 3y ago
- nr2x 3y agoProbably the best programming advice any anyone could get.
- jhanschoo 3y agoAs others mentioned, it's trivial* to write useful programs that provably halt; the impossible task is to determine if an arbitrary program halts. *: Trivial in a mathematician's sense
- hgsgm 3y agoIs there a name for the phenomenon where people who understand a concept don't talk about it because it isn't important or relevant, but people who don't understand think it's a big deal?