I am reading a text on Complexity theory. There is a set whose notation I cannot understand:

"Let $\sum$ = {0,1,#}"

From the context, and given that the book is used computer science courses, it seems like $\sum$ is the set which contains all combinations of bit strings up to length '#'.

In the text, a subset of $\sum$ is being used to define a set of palindromes in a Turing machine.

I would like to know more about this # symbol.

Another notation that I don't understand is in the following expression:

$x \in \{0,1\}^{n/4}$

What is the purpose of the $n/4$?

  • $\begingroup$ @Willie Wong: Thanks for that edit, was unaware of that tag. $\endgroup$ – ADB Jul 9 '13 at 17:56
  • $\begingroup$ stackexchange is organized as FAQ. You should better split it to two questions. $\endgroup$ – Jonas Stein Sep 20 '14 at 11:37

$\Sigma = \{0,1,\#\}$ means the set of these 3 symbols, which one usually calls alphabet in complexity theory. And $x\in \{0,1\}^{n/4}$ means that $x$ is a word of length $n/4$ over the alphabet $\{0,1\}$. These are exactly the same definitions as in mathematics, as 'word' means exactly the same as finite sequence which is a function from $\frac{n}{4} \rightarrow \{0,1\}$!

  • $\begingroup$ Great. Thanks so much! $\endgroup$ – ADB Jul 9 '13 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.