Questions tagged [decidability]
The decidability tag has no usage guidance.
79
questions
-1
votes
0
answers
56
views
Is it possible for two languages in NOT ( R E ∪ c o − R E ) to not have a reduction between them?
In computability theory, the class NOT(RE∪co−RE) refers to languages that are neither recursively enumerable (RE) nor co-recursively enumerable (co-RE). These languages are considered to be highly ...
6
votes
0
answers
105
views
Extensions of linear integer arithmetic decidable via Deterministic Pushdown Automata
I've recently learned about the connection between linear integer arithmetic (Presburger arithmetic) and Deterministic Finite Automata (DFAs). Namely, any formula in the first order theory of ...
- 161
2
votes
0
answers
82
views
When is an upper bound on the longest irreducible program outputting something computable?
This is a repost of this mathoverflow question.
Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program ...
- 567
-6
votes
1
answer
148
views
What is the correct halt status for an input to a simulating termination analyzer that calls its own termination analyzer? [closed]
What is the correct halt status for an input to a simulating termination analyzer that calls its own termination analyzer?
...
- 43
-1
votes
2
answers
157
views
Help understand why FOL wff are enumerable, but FOL is undecidable
I am very new to this. I am trying to understand some basics about what kinds of enumerations in FOL are possible, and which are not.
If you accept that FOL is defined in terms of a finite number of ...
- 107
1
vote
2
answers
476
views
Nondeterministic Turing Machines as deciders, versus NP and co-NP
While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step.
Deciding vs Recognizing: A Turing machine $M$ decides a language $L$ if whenever $s\in ...
- 378
0
votes
0
answers
66
views
Undecidability of games with limited hidden state
Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable.
Question:...
- 2,587
1
vote
0
answers
176
views
Decidability of the complexity of decision problems
This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
- 111
7
votes
1
answer
301
views
Is there a well-defined notion of an “R/poly” complexity class?
This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
- 353
4
votes
1
answer
297
views
Halting problem proofs that do not utilise self-reference or diagonalization
Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever?
All the duplicate questions I have come across end up ...
-13
votes
3
answers
1k
views
What happens when the Linz halting problem proof is based on simulation of the input?
Applying a Simulating Halt Decider to the Linz Halting Problem Proof
Of course it is obvious that no halt decider H can possibly return a correct halt status for any input defined to do the opposite ...
- 43
7
votes
0
answers
103
views
Algorithmically determining proof complexity for Frege systems?
I apologize if this falls wildly short of research level - I am just learning the very basics of proof complexity and lack any real logic background.
Let $F$ be a Frege proof system (a finite complete ...
- 171
-8
votes
1
answer
414
views
Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state? [closed]
Everyone knows that it is impossible for a TM halt decider to derive the correct halt status for any input that does the opposite of whatever value it derives.
When we take the conventional ideas of:
(...
- 43
2
votes
0
answers
94
views
Tenth Hilbert problem on interval arithmetic
What is the decidability status of Hilbert's Tenth problem interpreted over interval arithmetic?
In details, let $p\in\mathbb{Q}[x_1,\ldots,x_n]$ be a Diophantine polynomial. The problem is that of ...
- 1,704
3
votes
1
answer
157
views
How to solve an unification problem on $\mathbb{N}$?
Usually, the unification problem for two given terms $t$ and $s$ is to find a substitution $\theta$ such that $\theta t = \theta s$,
which is equal to finding the certain $\langle x_1 , \cdots , x_n \...
- 141
21
votes
2
answers
1k
views
Decidability of diophantine equations over {=, +, gcd}
It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...
- 892
15
votes
1
answer
705
views
Computability and continuity
Say $L_1$ and $L_2$ are computable languages. Let $f$ be a function $L_1 \rightarrow L_2$. Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(...
- 255
1
vote
0
answers
30
views
Decidability of regular partition construction given its existence
Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$.
If we know that $G$ is LL(...
- 111
3
votes
1
answer
460
views
Can the halting problem be solved probabilistically? [closed]
Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
- 134
3
votes
0
answers
158
views
Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?
I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
- 131
4
votes
2
answers
285
views
Dependence of decidability on the encoding of Turing machines
Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of ...
- 151
4
votes
1
answer
164
views
Deciding whether a 2nfa halts on every input on every branch
A 2nfa is a nondeterministic finite automaton that can move its head left or right on the input tape, or not. Is the following language known to be decidable?
$$
\textit{H}_{\mathsf{2nfa}} = \{ \...
- 143
0
votes
0
answers
47
views
Is this a proof that diophantine equation solutions can't be bounded by power towers?
From this 2017 paper on upper bounds for solutions to diophantine equations:
Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution
in positive integers x1, . . . , xn , then x1, ....
6
votes
1
answer
272
views
Decidability of rank-k polymorphism vs. System F
There's a paper by Kfoury from 1992, "Type Reconstruction in Finite Rank Fragments of
the Second-Order $\lambda$-Calculus", that proves that type inference for Curry-style rank-$k$ polymorphic lambda ...
- 335
0
votes
2
answers
241
views
Is the decidability of a language decidable? [closed]
Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?
Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
- 311
0
votes
2
answers
228
views
Turing meta-oracle
Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
- 119
-1
votes
1
answer
136
views
Gödel-Numbering of the Context-Sensitive Languages
I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
- 462
7
votes
1
answer
436
views
Uniform mortality problem for Turing Machines
Consider the following generalisation of the mortality problem for Turing Machines.
Given a Turing Machine $M$. Is there a bound $k_M$ such that starting
from any configuration $c$ machine $M$ ...
- 1,347
9
votes
1
answer
537
views
Is there an algorithm that finds the forbidden minors?
The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors.
Is there an algorithm that for an input $\mathcal G$ ...
- 14.1k
5
votes
1
answer
232
views
Post correspondence problem for finite monoids
The Post correspondence problem has the following version for finite monoids:
Input: a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$
Question: is ...
- 51
2
votes
1
answer
344
views
Petri net termination
Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example ...
- 191
2
votes
2
answers
212
views
How can you state how abstract interpretation gets around Rice's Theorem succinctly?
At this question, abstract interpretation has a nice in-depth look. However, I'd like someone to clearly and very precisely state how abstract interpretation takes the result of Rice's Theorem over ...
- 309
4
votes
2
answers
1k
views
Enumerating decidable languages
[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.]
Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
- 153
6
votes
1
answer
2k
views
Show that minimal CFG is undecidable via mapping reduction
Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.
The ...
- 395
1
vote
0
answers
100
views
Deciding reachability under iterated independent polynomial mapping
For any $1\leq i\leq m$, $f_i: \mathbb{Q}\rightarrow \mathbb{Q}$ is a polynomial mapping over $x_i$, where $\mathbb{Q}$ is the set of rationals. For $\vec{a}_0=(a_1, \cdots, a_m)\in \mathbb{Q}^m$, we ...
- 21
0
votes
1
answer
202
views
Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?
Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem？ In other words, could the Tarski–Seidenberg theorem subsume Buchberger's algorithm and Wu's ...
- 1,071
19
votes
1
answer
1k
views
Is equivalence of unambiguous context-free languages decidable?
It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free ...
- 464
5
votes
0
answers
96
views
Which computational models support bigotous programs?
A bigotous program is a program which decides if its input is semantically equivalent to itself. Of course, this is impossible in a Turing complete language due to Rice's theorem.
In fact, its pretty ...
- 481
4
votes
2
answers
626
views
About the decidability of sets enumerated in non decreasing order
It is well known that a set of numbers enumerable in nondecreasing order is
decidable. However, the typical proof, by cases on the finiteness of the
enumerated set, is not constructive. In general, it ...
- 631
5
votes
1
answer
539
views
Proof that the theory of rationals is convex
In Example 10.12 of the book The calculus of computation by Bradley and Manna, it is said
The theory of rationals is convex, as it is convex in a geometric sense.
How does the geometric sense of ...
- 153
6
votes
1
answer
336
views
Proof of decidability of type checking of calculus of (co)inductive constructions?
I often see it asserted that type checking is decidable for CIC, but I haven't seen it proven. Is there a good paper (or simple demonstration) of this?
- 213
18
votes
2
answers
897
views
Deciding whether a unary context-sensitive language is regular
It is a well-known result that the question
Does a context-free grammar generate a regular language?
is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case,...
- 5,101
35
votes
3
answers
3k
views
Turing Machine restrictions that render halting decidable
If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the ...
- 3,773
8
votes
0
answers
421
views
Decidability of existential first-order theory of reals with exponential
The first-order theory over the reals as an ordered field with polynomials is decidable with doubly exponential complexity. However, if we additionally allow the exponential function, that is $e^x$ ...
- 191
-1
votes
1
answer
150
views
Global satisfiability in LTL
In propositional linear temporal logic (LTL) over $\mathbb{N}$, it is decidable whether a formula $\varphi$ is satisfiable from time point 0.
Is it known to be un/decidable to check the ...
- 115
0
votes
2
answers
336
views
Are there any open problems concerning decidability? [duplicate]
I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.
- 119
9
votes
1
answer
242
views
Oracle-Decidability of Algebraic Independence
Consider numbers $x_1,...,x_n\in \mathbb{R}$ given by TMs $M_1,...,M_n$ such that $M_i$ approximates $x_i$ to an arbitrary precision (by allowing it to run longer and longer).
I am interested in the ...
- 5,616
6
votes
2
answers
281
views
FSM transducer sequential composition decidability
this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$....
- 11.1k
25
votes
2
answers
2k
views
Is it decidable to determine if a given shape can tile the plane?
I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using Wang tiles.
My question is whether it is also known to be undecidable to determine
if a single ...
- 3,773
5
votes
1
answer
239
views
Is algebraic dependency decidable?
A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a ...
- 5,616