Finite dimension – undecidable problems

Mikołaj Bojańczyk

zajęcia / courses

Finite dimension – undecidable problems

Theorem. The following problem is undecidable:
• input: a weighted automaton;
• question: is some word mapped to $0$ ?

The archetypical function that can be computed by a weighted automaton is mapping a string of digits to its interpretation as a fraction stored in binary (or ternary, etc) notation. This construction is described in the following lemma.

Lemma 1. For every alphabet $\Sigma$ there is a finite weighted automaton which computes an injective function to the strictly positive reals

$f : \Sigma^* \to \field_{>0}.$

Proof. Without loss of generality, assume that $\Sigma = \set{0,\ldots,n-1}$ . The idea is to treat an input $a_1 \cdots a_i$ as a fraction in base $n$ :

$\frac{a_1}{n} + \frac{a_2}{n^2} + \cdots + \frac{a_n}{n^i}$

The only problem with this solution is that trailing zeros are ignored. Therefore, the automaton adds an imaginary 1 to the end of the input. To implement this procedure by an automaton, we do the following. Its state space is $\field^2$ . The idea is that the first coordinate stores the value of the input seen so far, while the second stores $1/{n^{i+1}}$ where $i$ is the length of the input read so far. The initial vector is $(0,1/n)$ . For $a \in \Sigma$ , the state update function is the linear function

$\delta_a (x,y) = (x+ a \cdot y , \frac y n)$

The output function is

$(x,y) \mapsto x+y$

which corresponds to adding the imaginary 1 at the end of the output. $\Box$

For a Turing machine $M$ , define $\Sigma_M$ to be the work alphabet of the machine plus pairs of the form (letter of the work alphabet, state of the machine). A configuration of the machine is represented as a word over this alphabet, where exactly one letter is of the pair type, and describes the position of the head. For example, the word

$a b (a,q) b$

represents a configuration where the tape content is $abab$ and the head is over the third cell with state $q$ .

Below, by transducer we mean a deterministic finite automaton where each transition is labelled by possibly empty output word. This is a slightly more general model than the one in the lecture on determinisation.

Lemma 2. Let $M$ be a Turing machine. There exists a transducer

$s : (\Sigma_M)^* \to (\Sigma_M)^*$

such that if $c$ represents a configuration of $M$ , then $s(\rho)$ represents its successor configuration.

Proof. The automaton has a one letter buffer in case the head will want to move to the left. $\Box$

The following lemma shows some closure properties of functions recognised by weighted automata.

Lemma 3. Suppose that functions

$f,g : \Gamma^* \to \field$

are recognised by finite weighted automata, and let

$s : \Sigma^* \to \Gamma^* \qquad L \subseteq \Gamma^*$

be a transducer and regular language, respectively. Then the following functions are also recognised by finite weighted automata:
• the sum $f+g$ ;
• the scalar multiple $af$ for $a \in \field$ ;
• the composition $f \circ s : \Sigma^* \to \Gamma^*$ ;
• the function which is defined as $f$ on $L$ and as $g$ outside $L$ .

Proof. The sum and scalar multiple are immediate. For composition with a transducer, suppose that the state space of $f$ is $\field^n$ and the transducer $s$ has states $Q$ . Then the weighted automaton for the composition $f \circ s$ has state space $\field^{n \times Q}$ . After reading an input where the transducer would end up in state $q$ , the number stored in coordinate $(i,q)$ is the same as number stored in coordinate $i$ by the original weighted automaton, and it is zero otherwise. The “if then else” construction in the last item of the lemma can be seen as a special case of the transducer, by using a transducer which appends to the word a bit which says if the input belonged to $L$ . $\Box$

Suppose that $M$ is a Turing machine. We will construct a weighted automaton with input alphabet $\Sigma_M \cup \set \#$ such that the Turing machine has an accepting computation if and only if the automaton maps some nonempty word to $0$ . The automaton works as follows. Apply Lemma 1 to get an injective function

$f : (\Sigma_M \cup \set {\#})^* \to \field_{>0}$

and apply Lemma 2 to the machine $M$ yielding a transducer $s$ which computes the successor configurations of $M$ . Consider now the function

$g : (\Sigma_M \cup \set{\#})^* \to \field$

defined as:
• if the input is of the form

$c_1 \# c_2 \# \cdots \# c_n \qquad \mbox{with } c_i \in (\Sigma_M)^*$

where $c_1$ is the initial configuration over the empty input and $c_n$ is an accepting state, then the output is

$f(c_2 \# \cdots \# c_n) - f(s(c_1)\# \cdots \# s(c_{n-1}))$

• otherwise, the output is $1$ .
The definition of the function is defined in terms of the four closure operations given in Lemma 3, and therefore it is recognised by a finite weighted automaton. The only way for the function to output 0 is to get on input an accepting computation of the Turing machine.

zajęcia / courses

Finite dimension – undecidable problems

Finite dimension – undecidable problems

Leave a Reply