What type of Machine is the C Preprocessor?
theorangeduck.com
theorangeduck.com
This is one of those times when you're probably better off saying and thinking "unbounded" rather than "infinite". The point of a TM is not that it "literally" (to the extent that term applies anyhow) has "infinite" cells in it, the point is that there is no point in the computation in which it will reach for another cell and be told that there isn't one. (So there isn't even a way to represent that.) Many "infinite" things are better conceived of as "unbounded". For another example, "infinite lists" in Haskell. Obviously, they can not concretely manifest infinitely many cells in memory, but there is no point at which the runtime will reach for "the next cell" and be told it has reached the end of the list.
That is also why it's better to model our real computers with TM math, even though they obviously do not have literally infinite amounts of memory. As long as a software process runs along and is never told that it is out of memory when it asks for more, we get fairly TM-like behavior, or we get a crash if it does run out. By contrast, while the FSM model is in some sense more mathematically accurate, it is less useful for modeling real computers, since it is so weak.
I think this formulation also better intuitively explains why we use infinity so often in our proofs; by saying "and there's always another one if you want it", we remove the case where we have to handle there not being another one. And that case can get quite hairy, as anyone who has watched their machine self-immolate after it discovers it is out of RAM can attest to. :) (It can also be every bit as mathematically tedious to deal with, too.)
The further I got through grad school, the more I said "unbounded" rather than "infinite".
I think there's a huge difference between simply saying "unbounded" compared to going through that detailed explanation you just gave. In the latter case, it's very clear what the difference is. But without the explanation I'd guess that people will think something like this:
unbounded -> without bound -> infinite
http://en.wikipedia.org/wiki/Compact_space
*Infnite cardinality of points, not infinite in measure.
Also, by "we", I should clarify I mean discrete mathematicians and computer scientists, who are usually dealing in the discrete case. In the continuous case, infinities come up "for real" more often.
The difference between "bounded" and "infinite" is the difference between "measure" and "cardinality". That is , "bounded" refers to a notion of distance, while "finite" refers to a measure of count. There are bounded infinities (such as the set of all rational or numbers between 0 and 1), but there are no unbounded finities.
A container that contains finite objects of all sizes must be an infinite/unbounded container.
When infinity is the relevant concept, use it.
And as long as you're operating in a region that's not close to the edge, the edges don't make a difference to the outcome.
Likewise, while real machines are really DFA's since they have a finite amount of memory, thinking of them as having infinite memory is a much better approximation. And as long as you don't "get close to the edges" by e.g. trying to allocate more memory than your machine has available, it works perfectly.
There are some interesting kinds of Turing Machine which use limited tapes, rather than limited transition tables. For example, a monotone Turing machine can have heads which only move one way. They're useful for modelling demand-driven input and output (one read-only, monotone input tape, one write-only, monotone outpu tape and one read-write non-monotone work tape). Other machines that I've seen in research are 'enumerable-output machines', which can only edit their previous output if it ends up lexicographically higher, and 'Generalised Turing Machines' which can edit their output as long as each bit takes a finite number of steps to 'stabilise'. These machines have been investigated by Jurgen Schmidhuber, among others.
> The main argument against Turing completeness was that my implementation did not support unbounded recursion.
I’m almost sure they are Primitive recursive function, but I didn’t have time to write the complete proof. http://en.wikipedia.org/wiki/Primitive_recursive_function#Li...
> This is a fairly clear distinction and a compelling argument. Clearly there are languages where you can effectively express unbounded recursion function() { function() } and the C preprocessor is not one of them.
>* But there are a number of subtleties going on here. For example, if we consider the set of macros I created to be the "machinery", and the "language" to be the Brainfuck input to my system, then it is indeed Turing complete. That is - I have created machinery which can simulate Turing complete languages. Taking all the above definitions into account, consider how odd it is that Turing complete machinery can be expressed in a non Turing complete language.*
And from the “Brainfuck interpreter written in the C preprocessor”: https://github.com/orangeduck/CPP_COMPLETE
> Currently the maximum recursion depth is set to around 1000 and the data array size around 100. These can be easily extended but for now, as a general rule of thumb computations exceeding 1000 steps may not run.
Here is the problem. We can consider the one-step-interpreter: it’s a function that has as arguments a program, the current instruction index and the whole memory state, and this function computes the next instruction index and the next whole memory state. This one-step-interpreter is primitive recursive. He put that function inside a bounded loop, which is also implementable as a primitive recursive function.
So essentially he created an interpreter that runs a program for at most a fixed number of steps, where this number is an argument of the function (or worse, in this case a constant). Interpreter(Program, Memory, MaxSteps) is a recursive primitive function. To be Turing complete, he needs to write InterpreterForEverIfNecesary(Program, Memory).
With a fixed MaXSteps value, it can’t compute all recursive primitive function.
Cons (tape, head, state) (Cons (tape, head, state), (Cons ...)))
But since our program is total, we can only extract the first N states, for some finite N. Compare this to a Turing Complete language like Haskell, where we can also define an infinite stream of iterations, but we can also traverse this stream indefinitely.
That's deadly. Any machine with a finite number of states that cannot re-enter a state it has previously been in must necessarily halt on all input. That makes it strictly less powerful than even an FSM.
Yes.
> It seems self-evident that running forever can't be useful
Really? Do you not think that it might be useful for, say, an operating system to run forever?
Yes.
Can you provide a reference?
>> It seems self-evident that running forever can't be useful
Really? Do you not think that it might be useful for, say, an operating system to run forever?
It's nice when the OS has the option of shutting down deterministically.
So my point in saying that all useful programs halt was really to argue that all useful programs must have the constraint that they their behavior is always predictable, or controllable, in some sense. In a trivial way, computers are always predictable, but Turing proved that there are cases where it's impossible to predict the eventual outcome of a program in advance, i.e., the halting problem. In precise terms, the outcome (halt/not halt) of some programs is said to be undecidable or uncomputable. Undecidability is a hallmark of Turing machines. But since real programs are written by humans, who can't solve undecidable problems, real programs will never be able to gain any advantage from undecidable behavior.
If yes, then not being able to re-enter old states disqualifies C preprocessor as a turing complete machine by considering simple machine that goes left and right till the end of time. However, is it really an algorithm? If there is no output one could simply replace that with just empty machine that halts for sure, therefore it can be simulated in C preprocessor.
On the other hand, if this is not requirement then we know that every algorithm we have to simulate to prove turing completeness halts eventually, there is no ability to re-enter old states but if algorithm halts we could just add enough more states (finitely many) that allows it to finish.
Contrived example: One algorithm a Turing machine could perform would be to write the characters "TM" every two cells on its entire tape. The tape is unbounded, so this algorithm is, colloquially speaking, infinite. Clearly, you cannot simulate this with a halting machine like the C preprocessor.
But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts.
[1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...
http://lmgtfy.com/?q=turing+completeness
> in order to decide if certain machine is turing complete does one have to prove that it can also simulate infinite, not halting algorithms?
Yes.
And you're saying this based on what? Thanks for googling this for me, although the key-word was "comprehensive" not any definition.
> And you're saying this based on what?
Based on the definition of Turing-completeness, and the (trivial) fact that there exist Turing machines that do not halt. A Turing-complete system is, by definition, a system that can emulate any Turing machine. Because some Turing machines don't halt, any system that never halts cannot emulate a Turing machine that does not halt, and so by definition is not Turing-complete.
From wikipedia we read:
Turing completeness
A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.
From the first part I think compute means that from some input A there is output B. It is later explained in 'computable function' article:
Each computable function f takes a fixed, finite number of natural numbers as arguments. Note that the functions are partial in general, i.e. they may not be defined for every possible choice of input. If a computable function is defined for a certain input, then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function).
So if computable function is returning something that means it halts. We are able to compute every halting algorithm in preprocessor hence it is turing complete.
Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end).
There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.
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 is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.
The exact steps of a Turing Machine don't need to be emulated exactly, only the output needs to be the same. However, it's trivial to turn your back-and-forth example into a Turing-computable function:
Let's call your back-and-forth machine "M1" and, without loss of generality, let's say it starts at cell 0, moves to cell 1, then back to cell 0. We can then define a new machine "M2" which outputs a list of M1's head positions at each step, based on a direct simulation of M1. In other words, M2 will output 01010101010101.... forever, never halting.
The C preprocessor cannot simulate M2, precisely because it cannot simulate M1.
Also, note that we don't need to wait for a Turing machine to halt before we read its output. There are many useful programs which should not halt, like servers and operating systems.
CPP has been known to be abused by programmers as a general text processor, has anyone else started using another language to help them write C?
I bet these pre-processor programs were themselves written in C.