# Tag Info

Accepted

### Turing Machine restrictions that render halting decidable

A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example: Juris Hartmanis: Tape-Reversal Bounded Turing Machine ...
• 22.3k
Accepted

### Is it decidable to determine if a given shape can tile the plane?

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] ...
• 516

### A simple decision problem whose decidability is not known

It is unknown whether or not it is decidable to determine if a given shape can tile the plane, even for polyomino tiles.                     (...
• 3,703
Accepted

### Decidability of diophantine equations over {=, +, gcd}

($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$...
• 14.7k

### Turing Machine restrictions that render halting decidable

Considering how parameter passing to subroutines and a huge part of memory management in mainstream computer languages is stack based, an obvious and natural variation is to restrict the unbounded ...
• 3,013
Accepted

### What notable automaton models have polynomially-decidable containment?

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular ...
• 5,424

### What is the simplest computational model for which the emptiness problem is undecidable?

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 ...
• 22.3k

### Is it decidable to determine if a given shape can tile the plane?

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, ...
• 22.3k

### What notable automaton models have polynomially-decidable containment?

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment. A NFA is GFG if there is a ...
• 7,643
Accepted

### Computability and continuity

Let $L_1 = L_2 = \mathbb{N}$ and let $M \subseteq \mathbb{N}$ be a maximal set and let $L = \mathbb{N} \setminus M$ be its complement. Recall that $L$ is infinite, and that every computably enumerable ...
• 26.4k
Accepted

### Is there an algorithm that finds the forbidden minors?

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second ...
• 3,013

### What notable automaton models have polynomially-decidable containment?

A Non deterministic XOR automaton (NXA) fits your question. A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor ...
• 9,348

### A simple decision problem whose decidability is not known

A problem from Automata Theory. Input: A DFA $D$ over a binary input alphabet. Question: Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary? In ...
• 4,900
Accepted

### Are there any open problems concerning decidability?

Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number? This is currently not known to be either decidable or undecidable. (By ...
• 6,898

### Deciding whether a context-free language is regular

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages. Regarding DCFL, I have two references (from Hopcroft+Ullman 79): A regularity test for pushdown machines, ...
• 1,502

### Deciding whether a unary context-sensitive language is regular

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate ...
• 406
Accepted

### Is equivalence of unambiguous context-free languages decidable?

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 ...
• 108
Accepted

### Enumerating decidable languages

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 (...
• 8,546

### Post correspondence problem for finite monoids

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) \to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether ...
• 10.3k

### Decidability of diophantine equations over {=, +, gcd}

A something that might be too long for a comment, based on the previous answer by Emil. In the case you are interested in the complexity of such a logic, consider reading LICS'2015 paper by Joël ...
• 1,110

### A simple decision problem whose decidability is not known

Iterated maps on the interval (description from here): (very related to the problem proposed by Magnus Find) Let $F$ be a piecewise-linear map on the unit interval and $x$ a point in this interval. ...
Accepted

### Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?

For Buchberger, it depends what you want it for, but generally speaking the answer is no. First, as pointed out on the Wikipedia article, the complexity upper bound given by Tarski-Seidenberg is ...
• 35.5k

### What notable automaton models have polynomially-decidable containment?

Let me first mention that your problem is not symmetric and that if $M_1$ is an NFA and $M_2$ a DFA, then the inclusion problem is polynomial (simply because it amounts to test whether the complement ...
Accepted

### How can you state how abstract interpretation gets around Rice's Theorem succinctly?

To be as clear and concise as possible, I'd try saying this Abstract interpretation may only over-approximate properties of programs: the most precise abstract value of a program $P$ may be $a$, ...
• 13.1k
Accepted

### Solving problems by deciding a logic

I think the most spectacular example of this approach is Thomas Hales' proof of the Kepler conjecture (aka Hilbert's 18th problem). In the 1950s, Fejes Toth proved that the Kepler conjecture was ...
• 31.6k
Accepted

### Consistency and completeness of any arbitrary 3-valued logic?

Any logic defined semantically in a similar way is trivially consistent, as it has a model. Any finite-valued logic has a faithful translation into classical logic, hence its set of valid formulas, ...
• 14.7k

### Deciding whether a unary context-sensitive language is regular

This is essentially the same answer as above, but since a "more expedient" answer is sought, I'm mentioning this: (Also, this is my first post here, so forgive me if I'm posting a triviality!) ...
Accepted

### Uniform mortality problem for Turing Machines

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: ...
• 22.3k
Accepted

### Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the ...
• 14.7k
It's undecidable because we can interpret natural numbers (with addition and multiplication). For example, let $Ind(f)$ be the formula: $$f(0)=1 \land \forall x \ \big(f(x)=1 \to f(x+1)=1\big)$$ Now ...