Hacker News Reader

Comment by lisper | Hacker News Reader

You don't need higher order functions, but you do need lexical closures. C only has one stack, so it's a PDA. Strictly less powerful than a TM.

This is the reason lexical closures are so important. They are what let you "allocate" an infinite amount of memory so you can be Turing-complete without side-effects.

View on HN

It isn't clear that C is just A PDA. Without any destructive manipulation, C functions can use pointers to pass down and maintain a chain of contexts, so that each function potentially has random access to something at each stack level above it without having to pop anything.

Yes, that's true. But you can only do a finite number of dereferences from the current frame without being destructive.

Not so; you can recurse back up over that structure.

It's not quite that simple. It turns out that you're right, but it's much more challenging than just saying "recurse back up". The problem is that if you're recursing then you're not in the current frame. You can only do a finite number of dereferences from the current frame. That makes every frame effectively a PDA cell.

Now, that is not a proof (yet) because there's an additional wrinkle: pointer dereferencing lets you reach an arbitrary distance back up the stack in a single step, and that might be the thing that takes you from PDA-land into TM-land. But you only have a finite number of pointers in the current frame, and each of those can only be dereferenced a finite number of times in the current frame and so this is equivalent to just having a local copy of that finite amount of information in the current frame and so you're still a PDA.

Now, it turns out that argument is actually wrong. But figuring out why it's wrong is not so easy. It makes an interesting exercise writing an emulator for a two-stack machine in purely functional C. But you're right, it can be done.

Indeed, I can have a function like this:

   get_data_from_stack(parent_pointer, num_levels);

this function just recurses, decrementing num_levels until it hits zero, and chasing the parent pointers. With that, I have random access all over the stack.

Of course, C is ultimately a finite state machine because pointers have a fixed width. "sizeof pointer" is a constant expression. The absolute number of objects which can be addressed is finite. In an abstract program which doesn't use sizeof on pointers or work with their internal representation in any way, we can relax this model to allow an unlimited space; we just understand that we can have as many stack frames as we want and that somehow, the & operator in any one of them produces unique pointers.

No, that doesn't work. Because...

> Of course, C is ultimately a finite state machine because pointers have a fixed width.

Yes, but I'm willing to let that slide as long as you never do anything with a pointer but dereference one or compare two of them to see if they're equal (because you have to assume that to make any interesting computational model Turing-complete). But I'm not willing to let num_levels slide. If num_levels has a fixed width (and in C it would have to unless you show me how to build a purely functional bignum library) this solution won't work.

It really is not trivial to figure out how to make this work.

> C only has one stack

Sure

> so it's a PDA.

Wrong

Why wrong? Remember, we're talking about functional C here, so no destructive operations are allowed.

Something like Baker's Cheney on the MTA without actually collecting garbage. The "cheat" is that unbounded stack size implies unbounded pointer sizes, which means no finite alphabet, but "C without pointers" isn't C, and "finite stack/tape" isn't PDA/TM, so I think the "cheat" is fair :-)

OK, you're right. I concede the point.

Reply on news.ycombinator.com