<ol>
<li><p>A pushdown automaton is a particular case of ISM, so it is possible to recognize a context-free language with ISM.</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2014-01-22T20:48:18.420Z
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](http://www.cs.cmu.edu/afs/cs/academic/class/15671-f95/www/handouts/sm-basics/node8.html) 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.
Mike Izbicki
CC BY-SA 3.0
2014-01-23T00:17:51.400Z
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.
Denis
CC BY-SA 3.0
2014-01-22T20:02:24.347Z
2014-01-22T20:02:24.347Z
Denis
<p>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.</p>

<ul>
<li>Make the initial state accept if the empty string is in the language.</li>
<li>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.</li>
<li>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.</li>
</ul>

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

<p>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 &mdash; 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 <em>not</em> 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.</p>

CC BY-SA 3.0
2014-01-22T21:51:22.410Z
These ISM are not even finitely representable, so it makes no sense to ask for any algorithm producing them or taking them as input.
Denis
CC BY-SA 3.0
2014-01-22T22:25:57.057Z
@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).
Niel de Beaudrap
CC BY-SA 3.0
2014-01-23T15:37:08.723Z
In your presentation, a TM determinining accepting states is exactly a TM recognizing $L$.
Denis
CC BY-SA 3.0
2014-01-23T15:40:27.270Z
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.
Denis
CC BY-SA 3.0
2014-01-23T16:54:56.390Z
@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*.)
Niel de Beaudrap
CC BY-SA 3.0
2014-01-23T19:38:25.347Z
ok it makes a little more sense with an oracle formulation, but then nothing of the sort is decidable in such a setting. Even decidable things (like emptiness of a regular language) become undecidable if the regular language is given as an oracle (i.e. the oracle given to the machine is guaranteed to be regular). So it does not really say something meaningful...
Denis
CC BY-SA 4.0
2023-06-28T10:58:42.927Z
Is it really a binary tree, though? Not some graph? If a language L allows to repeat a syntactic structure more than once, it is either a graph or there is not one binary tree representing the language. And the depth of the tree would depend on the input. So to my untrained eye, it looks like you describe a less powerful subset of a DFA.
BitTickler
CC BY-SA 3.0
2014-01-22T20:38:20.103Z
2014-01-22T22:26:10.527Z
2014-01-22T22:26:10.527Z
Niel de Beaudrap
<p>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.</p>

<p>I have two questions: </p>

<ol>
<li><p>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?)</p></li>
<li><p>Is there an algorithm for determining how powerful an ISM is?  </p></li>
</ol>

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

CC BY-SA 3.0
2014-05-05T02:32:50.163Z
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.
Vectornaut
<automata-theory><turing-machines>
Difference between infinite state machines and turing machines
Mike Izbicki
# Difference between infinite state machines and turing machines

(Asked by: username_0 on 2014-01-22)

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?

**Tags:** automata-theory, turing-machines

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2014-01-22. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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](http://www.cs.cmu.edu/afs/cs/academic/class/15671-f95/www/handouts/sm-basics/node8.html) 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.  
> **username_2**: 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.  

---

### Answer by username_3 on 2014-01-22. Score: 18

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.

> **Comments:**
> **username_2**: These ISM are not even finitely representable, so it makes no sense to ask for any algorithm producing them or taking them as input.  
> **username_3**: @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).  
> **username_2**: In your presentation, a TM determinining accepting states is exactly a TM recognizing $L$.  
> **username_2**: 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.  
> **username_3**: @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*.)  
> **username_2**: ok it makes a little more sense with an oracle formulation, but then nothing of the sort is decidable in such a setting. Even decidable things (like emptiness of a regular language) become undecidable if the regular language is given as an oracle (i.e. the oracle given to the machine is guaranteed to be regular). So it does not really say something meaningful...  
> **username_4**: Is it really a binary tree, though? Not some graph? If a language L allows to repeat a syntactic structure more than once, it is either a graph or there is not one binary tree representing the language. And the depth of the tree would depend on the input. So to my untrained eye, it looks like you describe a less powerful subset of a DFA.  

---

