# Tag Info

23

According to the introduction of [1], The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes [4]. [1] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG] ...

15

I'm not sure whether this is what you're looking, but the phase transition in random SAT is an example. Let $\rho$ be the ratio of number of clauses to number of variables. Then a random SAT instance with parameter $\rho$ is very likely to be satisfiable if $\rho$ is less than a fixed constant (near 4.2) and is very likely to be unsatisfiable if $\rho$ is a ...

15

Probably you already got these in your bag :-) Two way one counter machine over unary alphabet (Minsky61). Two way weak counter machines (the counter has no effect on the computation but the machine halts if counter reaches zero) [1]. Quantum one counter automata [2]. With binary alphabets, the emptiness remains undecidable for: One way machines with one ...

14

An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation: Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a ...

10

The motivation you state for dealing with undecidability applies to decidable but hard problems as well. If you have a problem that is NP-hard or PSPACE-hard, we will typically have to use some form of approximation (in the broad sense of the term) to find a solution. It is useful to distinguish between different notions of approximation. Numeric ...

9

This is currently an open problem. As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem. On the other hand, the classical arguments for undecidability of the CFL universality problem make use of inherently ambiguous languages, and thus one needs new ideas to show ...

9

When you say "undecidable" I assume you mean it is independent of a theory such as ZFC. There will be statements like $$B(m)>n$$ (for natural numbers $m$, $n$) that are not decided by ZFC, assuming ZFC is consistent. Because otherwise we could compute the function $B$ just by searching for proofs in ZFC of such statements. Since $B$ is Turing complete ...

9

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (halts on all inputs) then $L(M')=L(M)$ and if $M$ is not total then $L(M')$ is finite. By request I'm burning the homework question and putting in the full proof....

8

Here's a quick sketch to show that there is no Turing machine to decide whether an arbitrary class of problems is decidable. I should clarify what I mean by class of problems: a class of problems $T$ is a Turing machine which enumerates the elements (natural numbers, say) of a recursively enumerable set one after the other, such that each element in the set ...

6

The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966)) The uniform mortality problem undecidability follows from the following: Theorem: A Turing machine is mortal if and only if it is uniformly mortal I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. ...

6

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a careful analysis of the running time would show that it is indeed a polynomial time reduction. Not every such reduction is polynomial time, however. You can observe ...

5

Like the Halting problem, Post's Correspondence Problem is undecidable in general. Ling Zhao's Master's thesis describes a large set of solvable instances of the PCP problem, including some "hard" instances. But I don't know if the size/density/measure of his set of solvable instances is on par with the Halting Problem result you cite. http://webdocs.cs....

5

Letting $L$ be the complement of the language of copies $\{ww \mid w \in \{a, b\}^*\}$, you get your statement. First, it is indeed recognized by a NCM — as is the complement of the language of palindromes. The NCM simply ensures that two positions in the input word chosen non deterministically hold different letters, and checks that they are separated by ...

5

While @LanceFortnow answered the question asked, since the OP mentioned deciders, I'll mention what kind of oracle is needed for that. Jockusch showed that the computable sets are $A$-uniform iff $A$ is of high Turing degree: $$A'\ge_T\emptyset''.$$ So it doesn't imply solving the halting problem, $$A\ge_T\emptyset'.$$ See Soare's book "Recursively ...

4

The problem is in your assumption that rational relations are closed under intersection. The following counter-example is taken from Example 2.5 in Berstel's "Transductions and Context-Free Languages": Let $X, Y \subseteq \{a\}^* \times \{b,c\}^*$ be rational relations defined by \begin{align*} X ={}& \{ (a^n, b^n c^k) \mid n,k \geq 0 \} \\ Y ={}& \{...

4

If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them. Your regularity theorem holds with length-preserving functions. If you want to allow length-increasing functions (that you need for PCP), you need a more powerful transducer model, for which undecidability quickly kicks in.

3

If you mean "undecidable" in the computational sense, then see the answer of Suhail Sherif. Your question becomes more interesting if we take "undecidable" in the proof-theoretic sense, i.e. there is no mathematical proof (say in ZFC) of $R\subseteq L(G)$ and no proof of $R\not\subseteq L(G)$ either. Such languages exist, because for any undecidable ...

3

Given an $R$ and a $G$, one can easily construct a TM which outputs whether $R \subseteq L(G)$. (Consider two TMs, one that just rejects and one that just accepts. If not the first, then the second TM would definitely be correct.) What is not possible is this: Give a TM that takes as input any $R$ and any $G$ and accepts iff $R \subseteq L(G)$ and rejects ...

2

The obvious candidates for these kinds of things are number theoretical. The collatz problem springs to mind, see What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?. The cited article is here, but it is about tag systems rather than number theory. Termination is, of course, undecidable, but of course ...

2

Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?". These algorithms (which may be randomized) are sometimes called "errorless heuristics" and have been studied in complexity theory, esp. average-case complexity; see e.g. this paper of Watson and ...

2

Your question is very brief, so my answer will be as well: Structure DecidableEquivalenceRelation := { carrier :> Type ; rel :> carrier -> carrier -> Prop ; reflexive : forall x, rel x x ; symmetric : forall x y, rel x y -> rel y x ; transitive : forall x y z, rel x y -> rel y z -> rel x y ; decidable : forall ...

2

Let me clarify one subtle point: first order logic is only undecidable for certain given languages. In particular the language $\cal{L}$ that contains only monadic predicates, that is, predicates of the form $P(x)$ and no function symbols, is decidable. If you allow function symbols or predicates with more than 1 argument, then $\cal{L}$ usually becomes ...

2

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e. Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate. Note that no requirement, even on ...

1

Pick M to be a universal Turing machine plus two states called A and B. If you enter state A, you stay in state A forever. If you enter state B, you go through some sequence that goes through all the states, ending in A. More detailed construction is left as an exercise to the reader, but this should be fairly straightforward. Now you can diagonalize. Make ...

1

I was also wondering how to solve this problem. Although the comments seem to suggest that the poster of the question has already solved the problem, I will write up a solution regardless in case anyone else is curious. Some credit goes to Sidhanth Mohanty. He showed me this question because he was also interested in the solution, and he provided some ...

1

A Mathematical Introduction to Logic, Second Edition: Herbert B. Enderton

1

One way to look at your question is the Busy Beaver Numbers. What we will do is restrict a Turing Machine so that: The blank symbol is a $0$ The tape alphabet is $\{0, 1\}$ The input to our turing machine is always nothing (the tape is always initialized to only containing $0$'s) There are only $n$ internal states, for some $n \in \mathbb{N}$. From here ...

1

This question is probably more suitable in cs.se, but until it gets migrated, here is an answer. Rice's theorem regards non-trivial semantic properties. Formally, a semantic property is a set of Turing machines $P$ such that for every two TMs $M_1,M_2$, if $L(M_1)=L(M_2)$, then either $M_1,M_2\in P$, or $M_1,M_2\notin P$. That is, membership in $P$ is ...

1

Very cool idea! Idea: We can exploit the comprehension axiom in ZF set theory to define a language that depends on an independent statement. Step 1: Take your favorite statement that is independent of ZF such as AC - the axiom of choice. Step 2: Define a language L = {x in {0,1} | x = 0 if AC and x = 1 if NOT AC}. Notice that L is either {0} or {1}. Now,...

Only top voted, non community-wiki answers of a minimum length are eligible