Teacher: And that concludes this lecture on Turing machines.

Eric: Cool! I didn't know all modern programming languages, such as C, are Turing complete!

Ilyssa: Lolwut? C isn't Turing complete.

Eric: How is it not? You can convert any Turing machine into a C program and vice versa.

Ilyssa: Actually you can't, because no C program can access an arbitrary amount of memory.

Eric: How so?

Ilyssa: Because pointers are fixed size. All types have a size which is defined in the implementation, each C implementation must define the maximum size, which is then fixed for that language. This means that there is a maximum pointer size defined in each C implementation as sizeof(void*), which means you can only access a fixed amount of memory.

Eric: Right, but you could add an external storage device to it.

Ilyssa: Which wouldn't change anything, because then it's C + external device that's Turing-complete and not C itself. This is like saying a finite state machine is Turing complete because if you add a tape to it then it becomes a Turing machine.

Stolen story; please report.

Eric: Wait so you're telling me, C has conditionals, loops, infinite recursion, and yet isn't Turing-complete?

Ilyssa: Right, because it can't address arbitrary memory. The return type of sizeof() is size_t which is an int or long, which is bounded. So you can't have arbitrarily large pointers.

Eric: What the hell is the point of all this?

Ilyssa: I guess it goes to show that real-world programming languages don't need to be Turing-complete to be useful for just about anything we might need them to do, practically, if even something as powerful as C isn't Turing-complete.

Eric: So the notion of Turing-completeness is basically irrelevant in the real world?

Ilyssa: I thought that was obvious.