# 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 ...
Accepted

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

According to the introduction of , 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 .  ...

### 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.                     (...
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 $|$, $+$...

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

### 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, ...
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 ...
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 ...

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

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

### 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 ...
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 (...

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

### Can you see that the Linz Halting Problem proof contains a fatal flaw?

This will come as no surprise to most people here, but Linz' proof does not appear to have a fatal flaw. I have prepared a machine checked formalization of the argument here. I didn't implement all ...
Accepted

### Is there a well-defined notion of an “R/poly” complexity class?

There is nothing stopping you from defining the class, though I don’t recall seeing it studied. Actually, I can see two reasonable definitions for this class. The first one, which follows more ...
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$, ...

### 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: ...