Skip to main content
Share Your Experience: Take the 2024 Developer Survey
31 votes
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 ...
Marzio De Biasi's user avatar
21 votes
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 $|$, $+$...
Emil Jeřábek's user avatar
19 votes

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 ...
Thomas Klimpel's user avatar
13 votes
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 ...
Andrej Bauer's user avatar
  • 29.1k
12 votes
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 ...
Thomas Klimpel's user avatar
10 votes
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 ...
Lorenzo's user avatar
  • 118
9 votes

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 ...
gdmclellan's user avatar
9 votes

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 ...
D.W.'s user avatar
  • 12.1k
9 votes
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 (...
Lance Fortnow's user avatar
9 votes

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 ...
Bartosz Bednarczyk's user avatar
8 votes
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 ...
Joshua Grochow's user avatar
8 votes
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 ...
Emil Jeřábek's user avatar
8 votes

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 ...
Dan Doel's user avatar
  • 1,021
8 votes
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 ...
Emil Jeřábek's user avatar
7 votes
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$, ...
cody's user avatar
  • 13.9k
6 votes
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: ...
Marzio De Biasi's user avatar
6 votes

Petri net termination

Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does not terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $...
Michael Blondin's user avatar
6 votes

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!) ...
Georg Zetzsche's user avatar
6 votes
Accepted

Nondeterministic Turing Machines as deciders, versus NP and co-NP

As requested, I write up my comment as an answer, hoping that I correctly understood the misunderstanding :-) Li-yao Xia's answer already clarifies that, in the context of complexity, there are only ...
Damiano Mazza's user avatar
5 votes
Accepted

Oracle-Decidability of Algebraic Independence

The answer is no; interestingly, the problem is harder to state satisfactorily in my opinion than it is to resolve! Roughly speaking, the subtlety which complicates the posing of the problem is that ...
Noah Schweber's user avatar
5 votes
Accepted

Proof of decidability of type checking of calculus of (co)inductive constructions?

I found another reference that goes through a detailed proof of the decidability of typechecking for systems of dependent types up to the CIC: Chapter 2 of Advanced Topics in Types and Programming ...
cody's user avatar
  • 13.9k
5 votes

Enumerating decidable languages

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$ ...
Bjørn Kjos-Hanssen's user avatar
5 votes
Accepted

Decidability of rank-k polymorphism vs. System F

The conclusion of [Kfoury & Tiuryn 1992] says (emphasis mine): We prove that [...] for every $k\ge 3$ there is a typing of constants that assigns types in $S(1)$ such that the type ...
Radu GRIGore's user avatar
  • 4,796
5 votes

Dependence of decidability on the encoding of Turing machines

For a given computable $f$, the decidability of $L_f$ is independent of the encoding of Turing machines if and only $f$ is eventually injective (i.e., there exists a finite $X\subseteq\def\N{\mathbb N}...
Emil Jeřábek's user avatar
4 votes
Accepted

Turing meta-oracle

Such an $H$ would let us solve the halting problem: We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$). If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)...
Noah Schweber's user avatar
4 votes
Accepted

Show that minimal CFG is undecidable via mapping reduction

Here is a solution based on a reduction from Post Correspondence Problem. The general idea is similar to the ones used in reductions from PCP to the emptiness of intersection and ambiguity in context-...
Sylvain's user avatar
  • 3,374
4 votes

About the decidability of sets enumerated in non decreasing order

Suppose there were a computable $f$ as described in the question. Then we could solve the Halting problem as follows. Given a Turing machine $T$, consider the computable function $g$, defined by $$g(...
Andrej Bauer's user avatar
  • 29.1k
4 votes
Accepted

Proof that the theory of rationals is convex

The key idea here is that for any conjunction of equations $F\equiv u_1=v_1\wedge\ldots\wedge u_k=v_k$, the set $S_F$ is convex in the geometric sense, i.e. for any two points $p,q\in S_F$, all points ...
Klaus Draeger's user avatar
3 votes

Turing Machine restrictions that render halting decidable

the phrasing of this question is slightly problematic because a Turing machine with a finite tape is arguably not much related to a Turing machine and closer to/ essentially a finite state machine. ...
vzn's user avatar
  • 11k
3 votes
Accepted

Dependence of decidability on the encoding of Turing machines

Claim: for any function $f:\{0,1\}^*\to\{0,1\}^*$ (not necessarily computable) and any admissible (see comments below) encoding, the language $$ L_f = \{\left<M\right> \mid M \mathrm{\ accepts\ }...
Aryeh's user avatar
  • 10.6k

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