I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class.

The question gives us a string $\alpha \in \{0,1\}$* and the function $\mathsf{int}(\alpha)$ that changes a binary number to its base 10 form. (example, $\mathsf{int}(00010) = \mathsf{int}(10) = 2$)

Now comes the tricky part: Define the language $L ⊆ \{0, 1, \#\}*$ by:

$L = \{\alpha\#\beta | α, \beta ∈ \{0, 1\}$* and $|\beta| ≥ \mathsf{int}(\alpha) ≥ 1 $ and $\beta \{ \mathsf{int}(\alpha) \} = 1 **\}$.

This bolded section is confusing me, and it seems like there are different variations of T.M. notation as well...

Could someone give me a rough approximation of what this might mean?

Extra: Examples for language $L$:
$\#111 \notin L$
$00010\#11100 \in L$
$00011\#010111 \notin L$
$00011\#11 \notin L$
$1\#\#1 \notin L$

Thanks in advance.


The function $\mathsf{int}$ actually doesn't change a binary number to its base 10 form. Rather, it takes a string encoding some number $n$ in binary, and outputs $n$. When we write the output, we use decimal (base 10), but the output is just a number. It's us who use base 10.

The language $L$ consists of all strings $\alpha\#\beta$, where $\alpha,\beta \in \{0,1\}^*$, such that

  1. $\alpha$ encodes (in binary) an integer $a$ in the range $1$ to $|\beta|$, where $|\beta|$ is the length of $\beta$.
  2. The $a$th bit of $\beta$ is $1$.

It's difficult to say what the $a$th bit of $\beta$ is, since there are several possible conventions:

  1. The "first" bit could be bit number $0$ or bit number $1$; in this case it seems like the first bit should be bit number $1$.
  2. We could be counting bits from the left or from the right; the usual convention is from the left, though if you think as a string as encoding a number, it is more natural to count from the right.

Assuming we are counting bits from the left and starting with $1$, $L$ consists of strings $\alpha\#b_1b_2\cdots b_n$ where $\alpha$ encodes a number $a$ in the range $1 \leq a \leq n$ and $b_a = 1$. This interpretation also matches your examples.


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.