Talk:Constructible function
Latest comment: 17 years ago by Neilc in topic Binary representation
 | This  level-5 vital article is rated Start-class on Wikipedia's content assessment scale.It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Binary representation edit
From the article:
- In the second definition, f is called time-constructible, if there exists a Turing machine M which, given a string 1n, 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 1n prints out 1f(n) in at most steps.
Neilc 06:05, 2 February 2007 (UTC)