HN2new | past | comments | ask | show | jobs | submitlogin

You can still try hard and cover many cases where it would go into an infinite loop. And then try even harder and cover even more cases.


And you still won't have written a program that determines whether any arbitrary program goes into an infinite loop.


If we can write a program that translates said arbitrary program into the rules for an n-state, m-symbol turing machine, where n = (2|3|4|5) and m = 2, then yes - we can determine if the program terminates or not.

We can make some fuzzy guesses whether or not the program terminates or not in other state/symbol combinations.

http://en.wikipedia.org/wiki/Busy_beaver

If we ever did write said program that could determine whether any /arbitrary/ program is infinite, then we have solved the halting problem. And that would be quite something.


You're right. I wouldn't have.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: