15
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ "Is there a solution for this system of Diophantine equations?" Is this what you're asking? It's not clear to me what you want. But, the problem I gave is undecidable and does not mention TM, so, strictly speaking, it would appear to satisfy the requirements of your second paragraph. $\endgroup$
    – rgrig
    May 6, 2012 at 22:18
  • $\begingroup$ Deciding if two pushdown automata recognize the same words is undecidable as well as other problems about pushdown automata. I can't think of undecidable problems involving DFAs. $\endgroup$
    – jmad
    May 6, 2012 at 22:39
  • 1
    $\begingroup$ The answer to the question "Is it possible to build an undecidable problem for an automaton less powerful than a Turing Machine" is yes. In fact, for every type of automaton one can always identify an undecideable problem. $\endgroup$
    – Amelio Vazquez-Reina
    May 7, 2012 at 14:05
  • 1
    $\begingroup$ Given the accepted answer, I rephrased the question to ask what the OP (apparently) wants. $\endgroup$
    – Raphael ♦
    May 10, 2012 at 14:21

5 Answers 5

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1, thanks, I'm still tempted to ask about a simpler than CFG, and so on.. to find out which is the first (simpler) known automata+problem to be undecidable $\endgroup$
    – Hernan_eche
    May 7, 2012 at 12:35
  • 3
    $\begingroup$ To find a "simpler" or "simplest" problem that's undecidable, or has any property, you'd need a precise definition of "simple", of which many are possible. But the classical one in automata and formal languages is "level in the Chomsky hierarchy" (which is not really much of a hierarchy, mathematically speaking -- it was originally propounded for natural language grammars). FSA is the lowest, and I'm pretty sure any undecidable problem for FSAs would have to refer in some "essential" way to "less simple" formalisms (all needing precise definition). CFL/CFG is next highest, so I picked that. $\endgroup$
    – David Lewis
    May 7, 2012 at 20:40
  • $\begingroup$ +1 I agree, find the minimal is undecidable too, surprisingly is not possible to build an undecidable problem for FSA, then is possible for CFG, is just tempting to find something in between, thanks $\endgroup$
    – Hernan_eche
    May 8, 2012 at 11:43
  • 1
    $\begingroup$ @Hernan_e -- there is a very rich structure of sub-CFL models and languages -- for example, the 1-counter pda/family, which uses a positive integer "counter" instead of a pda; the n-turn pda, which allows only a n turns from increasing to decreasing the stack, and generalizations of those. And there are lots of undecidable issues about those, as well as open questions about the structures, for example: is there a "minimal" non-regular CFL in some precise notion of "minimal". But this stuff is usually at the grad and/or research level. $\endgroup$
    – David Lewis
    May 8, 2012 at 15:04
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ do you have a ref on this? its not immed obvious how to convert PCP to this. fyi there are also some undecidable problems with FSM "transducers". $\endgroup$
    – vzn
    Oct 22, 2012 at 19:00
  • 1
    $\begingroup$ (1) You are right, it is in fact related to a two-tape problem, the bars indicating the second tape. (2) Relation to PCP as follows. PCP instance consists of two lists of words $(u_1,\dots,u_n)$, $(v_1,\dots,v_n)$. Now the regular language that codes PCP is $\{ u_1\bar v_1, \dots, u_n\bar v_n \}^+$, where $\bar v$ is the barred copy of $v$. I am afraid I do not have a reference. $\endgroup$
    – Hendrik Jan
    Oct 22, 2012 at 20:21
3
$\begingroup$

"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.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ The question of whether or not an LBA halts is also decidable for a TM, so it was not part of the examples I provided in my answer. Any problem that is undecidable for a TM is also undecidable for an LBA. $\endgroup$
    – Amelio Vazquez-Reina
    May 7, 2012 at 14:42
  • 1
    $\begingroup$ The second statement is false for any interpretation because the halting problem is recursive for LBAs but not for TMs. For TMs it's recursively enumerable, and if you want to stretch terminology and call both "decidable", then consider the co-halting problem for both -- recursive for LBAs but not even recursively enumerable for TMs. As for the first statement, anything "non-contrived" for finite state automata is recursive. We could always use "Does this FSA accept exactly $\{T|TM T halts on input T\}$ which is clearly not decidable, but that's contrived. That can probably be formalized. $\endgroup$
    – David Lewis
    May 7, 2012 at 17:46
  • 1
    $\begingroup$ @roseck -- first a correction: $\{T|\text{ TM } T(T) \text{ halts}\}$. Second I am quite confused by your statement and reply -- neither of your links justifies the statements that they display; both are general articles. $\endgroup$
    – David Lewis
    May 7, 2012 at 19:38
  • 1
    $\begingroup$ @DavidLewis roseck isn't claiming that an undecidable problem about TMs is still undecidable if you reinterpret it as being about LBAs. roseck simply states that if there is a problem that cannot be decided by TMs then the exact same problem with no reinterpretation also cannot be decided by anything a TM can simulate. The TM-halting problem and the LBA-halting problem are two different problems. $\endgroup$
    – Ben
    May 8, 2012 at 0:18
  • 1
    $\begingroup$ @Ben -- if so, then "...undecidable for any automaton that..." would have to be "by". But that is a trivial statement. $\endgroup$
    – David Lewis
    May 8, 2012 at 1:42
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.