@vzn btw this AMA, I am not sure whether there is some topic that will interest more people and I would write it nicely. Possibly one that I would describe better or know more.
@Evil again, the hover on the ad says "Turing machine blog" but the hovers seem not to work in meta posts, seems like they used to work, but maybe the SE code got messed up.
@Evil AMAs dont really "intrinsically" have a topic. its kind of the point. theyre fundamentally not like talks or interviews etc...
A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time-constructible if there exist a turing machine $M$ which computes $1^{T(n)}$ on input $1^{n}$ in $T(n)$ time.
Let $T_1$ and $T_2$ be two time-constructible functions in accordance to the definition above. I'm unable to prove the following...
@Auberon Well, I don't think I was ignoring the fact that the languages {} and Σ* are in P -- I think I called out those cases explicitly in the footnote, in the question you link to.
Why are they considered trivial? I'm not sure how to answer that one. Because they are trivial? There are a degenerate case, where it is straightforward (trivial) how to recognize them. Or, in other words, they are an exception that is not particularly interesting. That's what "trivial" means in this context, I guess.
We see this kind of thing in mathematics sometimes. For example, a prime number can be defined as a number that has no positive integer divisor other than 1 and itself -- except that we don't consider 1 to be prime, so we might consider that as a trivial case and word the definition to exclude that case.
A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time-constructible if there exist a turing machine $M$ which computes $1^{T(n)}$ on input $1^{n}$ in $T(n)$ time.
Let $T_1$ and $T_2$ be two time-constructible functions in accordance to the definition above. I'm unable to prove the following...
