Talk:Constructible function

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Template:Vital article

Binary representation

From the article:

In the second definition, f is called time-constructible, if there exists a Turing machine M which, given a string 1ⁿ, outputs the binary representation of f(n) in O(f(n)) time.

Why does the Turing machine need to output the binary representation of f(n)? Balcazar, Diaz, and Gabarro's Structural Complexity (ch. 2, pg. 45) notes:

f is time constructible if and only if it can be computed in O(f) steps. Here "computed" means that there exists a machine that on input 1ⁿ prints out 1^f(n) in at most

c\cdot f(n)

steps.

Neilc 06:05, 2 February 2007 (UTC)[reply]