@Raphael Thank you, seems like marvelous idea.

@Raphael yes, exactly what happened here. Well, then they will make lists instead of arrays? They should use the proper data structure for given task, and almost everyone got it right.

@Anon Mostly they are, and the vast open-ended questions seems to be bad starter, but if you are going to ask someone about what they like and do for years with passion - you might break the ice immediately. Also if someone is too busy, he will just inform you about it. Do not ruin the conversation before it actually started...

@Anon That they are, but advising students is also part of their job description. An undergrad asking to be coached towards research can be a waste of time, of course, but also an incredible boon. Prepare to be forwarded to a post-doc or PhD-student, but every group has open problems lying around.

@Evil Okay, so what's the problem? I'm confused now.

@Raphael almost = all - 1

Oh. Changing the sequence might not be that good, and there is no strong evidence of bad order.

@Evil You can't save everybody...

Save - no. But provide different examples, to teach something - yes. With yours and Juho's example it seems possible.

Earlier I meant that changing the order to show lists first might also fail in similar fashion.

@Evil True.

I guess I'd just impose running-time restrictions that are impossible to achieve with arrays. *shrug*

I mean, intuition is all fine, but they won't use lists unless they see the necessity. (I'm thinking of these "hashtables are the best dictionary implementation, period"-folks.)

@Raphael yeah, the most awesome example - you have 10^12 elements in the array, how many rewrites will it take to pull the first element out and put it at the end?

But it was too abstract to get it. Knowledge + intuition + necessity, that would be optimal. I just really want to avoid "if you have dictionary use hashes, if you have queue take list...".

@Gilles Turing Complete, sorry for common source. I understand that the void times size_t is a limit of variables, which depends on the underlying hardware (Also C gives lower bounds, in particular case pointless, since it is impossible to get more variables), but the common definition is by emulation of one-tape TM. But still bounded. So in fact we cannot say that any language is Turing complete, right?

But still it seems more like Linear Bounded Automaton, not just the Pushdown Automaton.

@Evil some languages are Turing-complete, or at least admit Turing-complete implementations.

The thing about C is that it mandates a finite amount of storage (at least storage in the form of variables that can be accessed far from their definition). Many languages don't.

An actual implementation on a computer is usually Turing-complete because it's limited to 2^32 or 2^64 bytes, but if you reach the limit, you could recompile the runtime for a 128-bit processor and resume the execution of the program.

You can't do that in C because the 128-bit runtime would not be the same language: the program printf("%d", sizeof(void*)) would have a different result.

@Evil why LBA rather than PDA?

@Gilles because we can do more powerful computation using C than simple PDA, we can go after NPDA with limited depth or TM with fixed memory, if I am not mistaken LBA > PDA and fits the restrictions given.

@Gilles thank you for the answer, I never thought before that C on different sizeof(void*) are different languages.

And also though that language powerful enough to emulate TM is Turing Complete itself.

I don't see how to encode a LBA in C. How do you go back to read the input?

The input from argv?

Or the stdin, not clearing it? Then using fseek to get back. Maybe this is bad direction.