News for hackers. Stuff that matters.
Re:What type of Machine is the C Preprocessor? by lisper on Tuesday January 28, 2014 @02:18AM (#7135828)
> I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'.

That is correct. But "producing the same output" means not halting when a TM does not halt. Otherwise it is not the same output.

But halting is actually a red herring in this case. Because the number of states that a cpp-machine can visit is finite, it is easy to construct a TM (or even an FSM) that halts on all inputs but produces a different output than any given cpp machine for some input. For example, a TM can do bignum arithmetic that halts on all inputs, but for some input it must be the case that such a TM will produce a different output than any given FSM, and hence any given cpp-machine, since cpp-machines are strictly less powerful than FSMs.

There are no comments on this comment yet.