6
$\begingroup$

Finite state machines (FSM) are strictly less powerful than turing machines (TM). But this is not the case with infinite state machines (ISM). For example, every TM can be embedded into some ISM. The opposite (that for every ISM there exists a TM that can be embedded within the ISM), however, is not true. We can construct a counterexample from any FSM by adding an infinite number of states and no transitions.

I have two questions:

  1. Are all ISMs equivalent to either a FSM or TM? (For example, does there exist an ISM that can recognize a context-free grammar, but nothing more powerful?)

  2. Is there an algorithm for determining how powerful an ISM is?

EDIT: If such an algorithm doesn't exist, are there any reasonable heuristics or rules of thumb?

$\endgroup$
  • $\begingroup$ Can someone explain why this question was downvoted? I don't see anything wrong with it, so I'm worried I'll make the same mistakes the author made if I dare to ask something here in the future. $\endgroup$ – Vectornaut May 5 '14 at 2:32
2
$\begingroup$
  1. A pushdown automaton is a particular case of ISM, so it is possible to recognize a context-free language with ISM.

  2. How would you give your ISM to the algorithm? Anyway a lot of problems are already undecidable for Pushown Automata (particular case of ISM) like equivalence or universality, so I guess the answer would be no for any reasonable question here.

$\endgroup$
  • $\begingroup$ I should have remembered about pushdown automata :) I was imagining the ISM would be specified in the same way that FSMs are traditionally presented. That is, as a 4-tuple, but where the sets are allowed to be infinite. This page has an example. I'm less interested in handling the general case, and more curious about what are some sufficient conditions that might occur in practice to recognize whether an ISM recognizes a regular language or something else. $\endgroup$ – Mike Izbicki Jan 22 '14 at 20:48
  • 1
    $\begingroup$ The "simplest" thing which is more powerful than FSM is PDA, (or counter automata i.e. PDA restricted to one stack symbol), and alreay for them it's undecidable whether they recognize a regular language. So I think any reasonable meaning of your question has answer No. $\endgroup$ – Denis Jan 23 '14 at 0:17
16
$\begingroup$

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like.

  • Make the initial state accept if the empty string is in the language.
  • Create two states for the strings 0 and 1, which the initial state branches to depending on whether the first symbol is 0 or 1. Label these $q_0$ and $q_1$. If either of the strings 0 or 1 are in $L$, make the corresponding state accept.
  • For a given $n \geqslant 1$, and for each state $q_x$ for $x \in \{0,1\}^n$, create two states $q_{x0}$ and $q_{x1}$, to which the state $q_x$ branches depending on whether the next symbol is 0 or 1. If either $x0 \in L$ or $x1 \in L$ is in the language, make the corresponding state accept. Having performed this for all $x \in \{0,1\}^n$, proceed to the next value of $n$, ad infinitum.

This produces an infinite state machine which decides the language $L$. In particular, it decides $L$ regardless of whether $L$ is even computable, and even regardless of its position in the arithmetic hierarchy. So not only can you have infinite state machines which have power intermediate between FSMs and Turing machines, you can make it have as much or as little power as you like.

As to algorithms, note that the ISMs constructed this way have the same structure for any language: an infinite balanced binary tree. It in essence also represents the language directly, in that it effectively is equivalent to an infinite boolean string representing the characteristic function of the language $L$. As such, the subset of these ISMs which represent regular languages is not recursively enumerable: there is no way to conclude after a finite number of steps that the language recognised is regular, because for any candidate language that the ISM recognises, there could always be some exception — but the ISM might still represent some more complicated regular expression, so neither can one conclude in a finite number of steps that the language it decides is not a regular language. The complete lack of compression in the description of the language (which is necessary to be able to represent arbitrary languages using a common structure) makes it effectively impossible to decide such problems.

$\endgroup$
  • $\begingroup$ These ISM are not even finitely representable, so it makes no sense to ask for any algorithm producing them or taking them as input. $\endgroup$ – Denis Jan 22 '14 at 21:51
  • 4
    $\begingroup$ @dkuper: sure, my answer is not "constructivist-safe": it talks about what is possible for ISMs as abstract mathematical objects, and never mind how they are specified. If you want to restrict to a "finite presentation" of an ISM, you can take the exact same tree-structure and limit the accepting states to a decideable language, as determined by some Turing Machine which always halts. Then you're restricted to the bottom level of the arithmetic hierarchy, but the answer remains otherwise the same (though the TM determining accepting states gives a new way for regularity to be undecideable). $\endgroup$ – Niel de Beaudrap Jan 22 '14 at 22:25
  • $\begingroup$ In your presentation, a TM determinining accepting states is exactly a TM recognizing $L$. $\endgroup$ – Denis Jan 23 '14 at 15:37
  • $\begingroup$ My point is that when you say "the subset of these ISMs which represent regular languages is not recursively enumerable", there is no way that they could be recursively enumerable before you fix a finite representation for them. $\endgroup$ – Denis Jan 23 '14 at 15:40
  • $\begingroup$ @dkuper: Given that my description is basically with respect to an oracle for a language L, you may interpret my answer as saying that there's no algorithm even with access to such an oracle. (Without the oracle, there isn't even anything for an algorithm to act upon.) $\endgroup$ – Niel de Beaudrap Jan 23 '14 at 16:54

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.