# A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others?

I'm interested in this restriction coming from the syntax naturally, as opposed to just being a normal Turing machine with a step-timer attached.

• Nice question! But likely more knowledgably answered at CSTheory StackExchange: cstheory.stackexchange.com – Joseph O'Rourke Feb 4 '12 at 2:28
• Why do you object to the step-timer method? Doesn't this provide a way of satisfying your formal requirement syntactically, while also clearly computing exactly the polynomial time algorithms? – Joel David Hamkins Feb 4 '12 at 2:48
• See also related question: mathoverflow.net/questions/28056/… – Joel David Hamkins Feb 4 '12 at 2:50
• @Joel: the motivation is perhaps clearest in the case of logspace. If $f$ and $g$ are logspace-computable, then so is $f \circ g$, but the implementation of this is surprisingly delicate, since you have to dovetail the execution of $f$ and $g$ to incrementally produce the bits of $g$'s output to feed to $f$. So it's natural to look for programming languages/logics where the composition operation is algebraically well-behaved and does not require any tricky coding games. – Neel Krishnaswami Feb 5 '12 at 3:43