Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

When talking about Turing completeness I use an alternate definition of infinity that I call practically infinite: for a given a program that halts on an arbitrary Turing machine it also halts on this specific on. I call this practical Turing completeness (though I suspect the literature has already considered this idea and has a different term)



Could you be more precise, please? I'm afraid I don't understand the definition you've given. Can you make your quantifiers explicit?


I mean that the technical limits are a not an issue for the program you want to run. Hello World will run on an AppleII computer, but it doesn't have enough memory to run Libre Office (Assume an unlimited budget to create/port the compiler, POSIX layer, X server ...)

If the conversation is concerned with running Hello world it doesn't matter that an AppleII can't do everything, for our purposes it can do anything. If we expand the conversation a little but though we realize this machine is unable to run many things we find useful today.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

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

Search: