Hacker News Reader

Comment by arcbyte | Hacker News Reader

You are pedantically correct and wrong. Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory. Rather than go so esoteric as to say that only programs structured with fseek are Turing complete, we generally just make the jump from languages able to use arbitrarily sized RAM to assuming infinite RAM and say youre turing complete enough for most purposes.

View on HN

> Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory

I should've explained that I'm not talking about a physical implementation, but about the theoretical bounds of the C abstract machine.

Talking theoretically, since size_t is defined as:

> size_t can store the maximum size of a theoretically possible object of any type (including array).

In a proper theoretical turing machine, size_t would allow you to create and address arbitrarily large arrays too.

`sizeof(size_t)` and `size_t x; sizeof x` must be constant expressions. It is possible to create a c implementation where the size of a pointer is arbitrarily large, but it can't grow/isn't infinite.

For any give C implementation, it is thus trivial to theoretically solve the halting problem (assuming no stdio.h stuff is used).

Speaking in so much the abstract that it becomes absurd (which also can be used to prove your point, but bear with me here), since `size_t` is required to hold the size of any object, and a turing machine has infinite memory, then size_t would also need to be infinitely big, and `sizeof(size_t)` would be a constant returning infinity.

So, I don't think it having to be a constant is a problem as much as having to deal with infinitely big numbers inside of infinite memory (which may or may not be a contradiction, depending on axioms used to define a turing machine. I still need to work my way through annotated turing).

Of course, things do get a lot simpler and grounded using IO functions like you said earlier.

I don't think infinitely large integer constant area construct that makes sense.

As far as I'm aware, there isn't an instance of an infinitely large integer, even in mathematics, there are finite integers and there is the concept of infinity. (And size_t is defined as an unsigned integer type)

I'd argue you could use non-standard integers that are unable to be reached in a finite amount of steps but aren't infinity and are still "integers".

> unable to be reached in a finite amount of steps but aren't infinity

I don't see how such numbers can exit/be used/defined in any meaningful way. Do you have an example of such a number?

Reply on news.ycombinator.com