It's still Turing complete (though that's not saying much really). You can always grow the stack more :P

I don't think that solves the problem. Whatever fixed stack size you choose, you still cannot write a program that determines the size of the lists at runtime. A Turing complete system would have to be able to do that.

The only way I see is to allocate (almost) the entire machine memory to the stack, create one giant array in that chunk of memory and then put all lists in that single array. That's tantamount to reimplementing malloc on the stack.

Any physical machine cannot be Turing complete because it has a finite amount of RAM.

Sure, but we're talking about whether or not this particular style of C can be Turing complete and I'm not sure it is, even on a machine with an infinite amout of RAM.

A machine with an infinite amount of RAM can have an infinite stack size.

C arrays that live on the stack have to be created with a constant size (at least before C99). It's a limitation of the language regardless of any machine or stack size.

If we're going to grant that a machine can have infinite ram, surely we can grant that a spec of C can have infinite stack allocated arrays... :)

That's already been granted in this argument. The question now is, given an infinite stack, is this programming style Turing-complete?

Address space is not limited by RAM. The only concern is fixed vs expandable width address.

That is a purely theoretical concern, not a practical blocker against any program anyone would ever run.

A program that determines the number of items it needs to store in a list only at runtime doesn't seem that theoretical to me.