# Tag Info

2

Yes, of course. $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times. The answer to your other questions are also yes, by the time hierarchy theorem.

2

I don't see any obvious reason why the compiler could not inline the call to list_traverse, assuming that it is a simple and that its definition is available in the translation unit. But apparently it doesn't. (Actually, I do see an obvious reason: "It would be a lot of work, and the benefit might not be great." Not saying that that statement is necessarily ...

1

A simple way to do it is to just write an interpreter that follows the transition table. I.e., do something like (in C): state = INITIAL; symbol = get_next(); while(symbol != END) { state = table[state][symbol]; symbol = get_next(); } if(is_accepting(state)) /* Accept */ Next simpler is to write a rat's nest of gotos, transferring among them ...

1

From "Back to Direct Style" by Oliver Danvy: Much work has been devoted to transforming programs into continuation-passing style (CPS). ... By contrast, programs that are not in CPS (e.g., programs before CPS transformation) are said to be in "direct style" (DS). Their procedure calls can occur anywhere (i.e., not necessarily in tail position). In ...

Only top voted, non community-wiki answers of a minimum length are eligible