4 ms·
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 r
by lisper 10y ago
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.
- cronjobber 10y ago> C only has one stack Sure > so it's a PDA. Wrong
- lisper 10y agoWhy wrong? Remember, we're talking about functional C here, so no destructive operations are allowed.
- cronjobber 10y agoSomething 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 :-)
- lisper 10y agoOK, you're right. I concede the point.
- kazinator 10y agoIt 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.
- lisper 10y agoYes, that's true. But you can only do a finite number of dereferences from the current frame without being destructive.
- kazinator 10y agoNot so; you can recurse back up over that structure.
- lisper 10y agoIt'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.
- kazinator 10y agoIndeed, 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.