Turing Machine notation

Question

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.

Answer 1

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.