{"id":730,"date":"2015-10-27T10:06:04","date_gmt":"2015-10-27T09:06:04","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=730"},"modified":"2015-10-27T10:06:04","modified_gmt":"2015-10-27T09:06:04","slug":"finite-dimension-undecidable-problems","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/3-weighted-automata\/finite-dimension-undecidable-problems","title":{"rendered":"Finite dimension \u2013 undecidable problems"},"content":{"rendered":"

Theorem.\u00a0<\/strong>The following problem is undecidable:
\n\u2022 input: a weighted automaton;
\n\u2022 question: is some word mapped to \"0\"?<\/p>\n

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.<\/p>\n

Lemma 1. <\/strong>For every alphabet \"\Sigma\"\u00a0there is a finite weighted automaton which computes an injective function to the strictly positive reals <\/p>\n

  <\/span>   <\/span>\"\[f : \Sigma^* \to \field_{>0}.\]\"<\/p>\n

Proof. <\/strong>Without loss of generality, assume that \"\Sigma = \set{0,\ldots,n-1}\".\u00a0The idea is to treat an input \"a_1 \cdots a_i\" as a\u00a0fraction in base \"n\": <\/p>\n

  <\/span>   <\/span>\"\[\frac{a_1}{n} + \frac{a_2}{n^2} + \cdots + \frac{a_n}{n^i}\]\"<\/p>\n

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. \u00a0The initial vector is \"(0,1/n)\". For \"a \in \Sigma\", the state update function is the linear function <\/p>\n

  <\/span>   <\/span>\"\[\delta_a (x,y) = (x+ a \cdot y , \frac y n)\]\"<\/p>\n

The output function is <\/p>\n

  <\/span>   <\/span>\"\[(x,y) \mapsto x+y\]\"<\/p>\n

which corresponds to adding the imaginary 1 at the end of the output. \"\Box\"<\/p>\n

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 <\/p>\n

  <\/span>   <\/span>\"\[a b (a,q) b\]\"<\/p>\n

represents a configuration where the tape content is \"abab\" and the head is over the third cell with state \"q\".<\/p>\n

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.<\/a><\/p>\n

Lemma 2.\u00a0<\/strong>Let \"M\" be a Turing machine. There exists a transducer <\/p>\n

  <\/span>   <\/span>\"\[s : (\Sigma_M)^* \to (\Sigma_M)^*\]\"<\/p>\n

such that if \"c\" represents a configuration of \"M\", then \"s(\rho)\" represents its successor configuration.<\/p>\n

Proof.\u00a0<\/strong>The automaton has a one letter buffer in case the head will want to move to the left. \"\Box\"<\/p>\n

The following lemma shows some closure properties of functions recognised by weighted automata.<\/p>\n

Lemma 3. <\/strong>Suppose that functions\u00a0<\/p>\n

  <\/span>   <\/span>\"\[f,g : \Gamma^* \to \field\]\"<\/p>\n

are\u00a0recognised by finite weighted automata, and let <\/p>\n

  <\/span>   <\/span>\"\[s : \Sigma^* \to \Gamma^* \qquad L \subseteq \Gamma^*\]\"<\/p>\n

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

Proof. <\/strong>The sum and scalar multiple are immediate. For composition with a transducer, suppose that the state space of \"f\" is\u00a0\"\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\". \u00a0\"\Box\"<\/p>\n

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

  <\/span>   <\/span>\"\[ f : (\Sigma_M \cup \set {\#})^* \to \field_{>0}\]\"<\/p>\n

and apply Lemma 2 to the machine \"M\" yielding a transducer \"s\" which computes the successor configurations of \"M\". Consider now the function <\/p>\n

  <\/span>   <\/span>\"\[g : (\Sigma_M \cup \set{\#})^* \to \field\]\"<\/p>\n

defined as:
\n\u2022 if the input is of the form<\/p>\n

  <\/span>   <\/span>\"\[c_1 \# c_2 \# \cdots \# c_n \qquad \mbox{with } c_i \in (\Sigma_M)^*\]\"<\/p>\n

where \"c_1\" is the initial configuration over the empty input and \"c_n\" is an accepting state, then the output is<\/p>\n

  <\/span>   <\/span>\"\[f(c_2 \# \cdots \# c_n) - f(s(c_1)\# \cdots \# s(c_{n-1}))\]\"<\/p>\n

\u2022 otherwise, the output is \u00a0\"1\".
\nThe definition of \u00a0the 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.<\/p>\n","protected":false},"excerpt":{"rendered":"

Theorem.\u00a0The following problem is undecidable: \u2022 input: a weighted automaton; \u2022 question: is some word mapped to ? 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":634,"menu_order":3,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-730","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/730"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=730"}],"version-history":[{"count":34,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/730\/revisions"}],"predecessor-version":[{"id":764,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/730\/revisions\/764"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/634"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}