Hacker News new | ask | show | jobs
by rtb 683 days ago
You are technically correct, but this is still a pointless argument to make.

It's pretty easy to see that any finite machine isn't Turing Complete, because you just ask whether it can compute a function that doesn't fit in its memory. So, for your laptop: define a function that's true on some number larger than would fit in 16GiB (fiddling the definitions as necessary depending on exactly how you define input / output etc.)

As wikipedia says:

> No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete.

The convention is to ignore the infinite case, when talking about real systems because a) most things we want answers to are not large enough for this to make a difference and b) otherwise no real system is Turing-complete, and that's not a helpful definition.

1 comments

This isn't about physical systems. It's about programming language specs. Most programming languages are Turing complete as specified. C isn't. That's interesting.