Are there undecidable properties of non-turing-complete automata?

Question

Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability).

I would like to get an example (if possible) of an undecidable problem that is defined without using Turing machines explicitly.

Is Turing completeness of a model necessary to support uncomputable problems?

Answer 1

Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia...

1. Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?

2. Given two CFGs, do they generate the same language?

3. Given two CFGs, can the first generate all strings that the second can generate?

There are many others about CFGs/PDAs as well as CSGs/LBAs and many other "simpler than TM" models.

Answer 2

It is not clear what you are asking in the later part of the question mainly because "a problem about a machine model" is not defined.

I would like to get an example(if possible) of undecidable problem without needing Turing Machine

Let be $\{M_i\}$ be a class of machines and lets use $i$ as the code of $M_i$. We can interpret $i$ also as the code of $i$th TM and then ask that given $M_i$ does the $i$th TM halt? And this problem about $M_i$s is undecidable.

A language is just a set of strings, what interpretation you assign to the strings has no effect on the decidability of the language. Unless you formally define what you mean by a machine model and a problem about those machines your later questions cannot be answered.

Is Turing complete the minimal machinery to support an undecidable problem?

Again, the point I mentioned above applies. A more reasonable question would be: are all undecidability proofs go through something similar to the undecidability of halting problem for TMs? (The answer is: there are other ways).

Another possible question is: what is the smallest subset of TMs where the halting problem for them is undecidable. Obviously such a class should contain problems which do not halt (otherwise the problem is trivially decidable). We can easily create artificial subsets of TMs where the halting problem is not decidable without being able to compute anything useful. A more interesting question is about large decidable sets of TMs where the halting is decidable for them.

Here is another point: as soon as you have very small ability to manipulate bits (e.g. a polynomial size $\mathsf{CNF}$) you can create a machine $N$ with three inputs: $e$, $x$, and $c$ such that it output 1 iff $c$ is a halting accepting computation of TM $M_e$ on input $x$. Then you can ask the problems like: is there a $c$ s.t. $N(e,x,c)$ is 1? which is an undecidable problem.

Answer 3

There is a very simple undecidable problem for finite state automata. Break the alphabet into two halves $\Sigma \cup \bar\Sigma$, where the letters in $\bar\Sigma$ are "barred" copies. Now, given a finite state automaton $A$ over $\Sigma\cup\bar\Sigma$ decide whether it accepts a string such that the unbarred part equals the barred part (if we ignore the bars). E.g., string $a a \bar a \bar a b\bar b \bar aa$ would be ok (both parts spell $aaba$).

Yes, this is Post Correspondence Problem hidden in a finite state automaton. The Turing completeness is far from obvious in the question. It is there, in the background, as the two copies (unbarred and barred) together code a queue, which itself is of Turing power.

Answer 4

"Is it possible to build an undecidable problem for an automaton less powerful than a Turing Machine?"`

Yes. An automaton is a consistent axiomatic formulation of number theory (e.g. see (1)) and therefore by Gödel's 1st incompleteness theorem it must include undecidable propositions.

Example:

Any problem that is undecidable for a TM is also undecidable for any automaton that a TM can simulate. Why? Because if an automaton that is less powerful than a TM could decide a language that a TM cannot decide, a TM should be able to decide it by simulating the automaton with yields a contradiction.

Answer 5

Emil Post wanted to find the answer to exactly this question: Is there a non-recursive (non-computable) set which does not solve the halting problem. He succeeded only in part, but what he did, was create what is called simple sets.

From Wikipedia:

A subset of the naturals is called simple if it is co-infinite and recursively enumerable, but every infinite subset of its complement fails to be enumerated recursively. Simple sets are examples of recursively enumerable sets, that are not recursive. Have a look at the Wikipedia article for more information and references, simple set.