Definition feels contradictory (Computational Complexity Theory)

I studied a definition for time complexity: Let $$M$$ be a deterministic Turing Machine. The running time of $$M$$ is said to be:

for a function $$t: \mathbb{N} \to \mathbb{N}$$ ($$\mathbb{N}$$ is natural number) and for all $$x$$ belonging to $$\Sigma^*$$, $$M$$ halts in at most $$O(t(|x|)$$ steps.

My question is that $$x$$ belonging to $$\Sigma^*$$ means $$x$$ could very well be $$\varepsilon$$ (empty string) for which $$|x| = 0$$. How is $$t(0)$$ computed as 0 is not a natural number.

• en.wikipedia.org/wiki/Natural_number Commented May 22 at 17:50
• Wikipedia/Is 0 a natural number? That's a fun discussion!! Thanks for the laughs
– Stef
Commented May 22 at 18:36
• Is that word for word the definition in the book? It's weird. "For all x, M halts in at most O(t(|x|)) steps"? If x is already quantified by "for all", then t(|x|) is a constant and it doesn't make sense to talk about big-O...
– Stef
Commented May 22 at 18:39
• @Stef yes, and the same has been mentioned for s(|x|) where 's' is the space complexity function. I think O(t|x|) point is irrelevant in discussion as the entire point of using big-O is to ignore certain stuff like multiplication by constants and lower order terms. What's really bothering me is that I am not able to understand what part of this definition feels weird, is it 0 being a natural number (or not) or is it x belonging to Σ*. Commented May 23 at 6:26
• @OM_anand Whether or not |x|=0 is allowed by the definition really couldn't matter less. The only thing important in the definition is what happens in the limit. You could add any arbitrary constraint like |x| > 0 or |x| > 1 or |x| > 42 or |x| > 137 in that definition and the resulting definitions would all be equivalent. What is important in that definition is what happens when |x| grows, not when |x| is small. But the definition is a bit sloppily written.
– Stef
Commented May 23 at 13:22

$$\mathbb{N}$$ can be defined as the set of non-negative integers 0, 1, 2, ...
However, there is no contradiction regardless of how $$\mathbb{N}$$ is defined. It might just be a tiny mistake that I'm sure you're able to fix.