Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [undecidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
43 views

For which k can we decide whether an input k-gon tiles?

Can we decide whether a given polygon can tile the whole plane? First, let me briefly summarize what is known about this problem. If we only allow translations, then the problem is always decidable in ...
domotorp's user avatar
  • 14k
8 votes
1 answer
243 views

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

The question: Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM? I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} ...
Neal Young's user avatar
  • 10.8k
7 votes
2 answers
210 views

How to show that a problem is in $\Pi_1^1$?

I am trying to show that a decision problem is in $\Pi_1^1$. Because of this, I am looking for: Papers or books that present a complete and well-explained proof where a problem is shown to be in $\...
David Carral's user avatar
0 votes
0 answers
31 views

Decidability of Mixed-Integer Semidefinite Programs

Semidefinite programs (SDP) have an "efficient" solution, as a convex problem, by e.g. the ellipsoid method; but this comes with standard caveats as the output can be exponentially long (...
Alex Meiburg's user avatar
4 votes
1 answer
246 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 ...
Alan Whitteaker's user avatar
-13 votes
3 answers
1k views

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

Applying a Simulating Halt Decider to the Linz Halting Problem Proof When a simulating halt decider correctly simulates N steps of its input it derives the exact same N steps that a pure UTM would ...
polcott's user avatar
  • 59
0 votes
1 answer
222 views

Understanding the construction of an uncomputable function

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question. Theorem 1.10 There exists a ...
zxcv's user avatar
  • 109
-8 votes
1 answer
397 views

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state? [closed]

...
polcott's user avatar
  • 59
7 votes
0 answers
138 views

Halting problem for finitary PCF

Is the halting problem decidable for finitary PCF? By "halting problem" I mean the problem of deciding whether a closed PCF term evaluates to bottom under the denotational semantics of PCF. ...
PaR's user avatar
  • 71
-3 votes
1 answer
88 views

Show that membership in L is undecidable [closed]

Let L ⸦ {0, 1}* be the language {(M, x) | Turing Machine M on input x enters every state of M at least once}. How can I show that membership in L is undecidable?
Kwaku's user avatar
  • 5
0 votes
0 answers
45 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, ....
ghosts_in_the_code's user avatar
6 votes
1 answer
160 views

What is the minimal class of subshifts for which conjugacy is known to be undecidable?

The question of whether two finite one directional shifts are conjugates is known to be decidable. The same question for sofic shifts is famously open. I have seen that some works manage to prove ...
Shaull's user avatar
  • 5,646
2 votes
0 answers
111 views

How hard is it to determine ex(n,G)?

Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known ...
domotorp's user avatar
  • 14k
7 votes
1 answer
432 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$ ...
Bartosz Bednarczyk's user avatar
11 votes
1 answer
716 views

Non-comparable natural numbers

The "name the biggest number game" asks two players to write down a number secretly, and the winner is the person who wrote down the larger number. The game commonly allows players to write down ...
Stella Biderman's user avatar
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 ...
sixpanbass's user avatar
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 ...
Jára Cimrman's user avatar
-2 votes
1 answer
386 views

A variant of the Post Correspondence problem

Given words $\alpha_1, \ldots \alpha_n$ and $\beta_1, \ldots, \beta_n$, Post's Correspondence Problem asks if there is a sequence $i_1, \ldots, i_k$ of indices such that $\alpha_{i_1} \ldots \alpha_{...
Matei's user avatar
  • 1
1 vote
2 answers
231 views

Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

Edit: I originally defined a regular function as a function computable by a Mealy machine, but Denis pointed out that that was a weaker model than what I was thinking of. So to be more precise, by a "...
BenW's user avatar
  • 113
9 votes
1 answer
239 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 ...
Shaull's user avatar
  • 5,646
3 votes
1 answer
891 views

Real number $p$ such that a $p$-coin makes the undecidable decidable [closed]

This is an exercice from Arora & Barak, Chapter 7 : Describe a real number $p$ such that given a random coin that comes up "heads" with probability $p$, a Turing machine can decide an ...
Manuel Lafond's user avatar
4 votes
1 answer
361 views

Polynomial-time reductions between undecidable languages

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem. ...
Andrew's user avatar
  • 284
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 ...
Joseph O'Rourke's user avatar
-3 votes
1 answer
423 views

Consequences of polynomial time algorithm to variant of integer factorization

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring. So supposing ...
Turbo's user avatar
  • 12.9k
0 votes
2 answers
320 views

Example of R and G when $R \subseteq L(G)$ is undecidable [closed]

Could anybody provide an example of regular language R and context-free grammar G such that $R \subseteq L(G)$ is undecidable. Of course, if such language could be constructed. Thanks.
gsv's user avatar
  • 421
-1 votes
1 answer
169 views

Undecidable Single Programs [closed]

So the halting problem basically states that there cannot exist any finite length algorithm for automatically verifying if other finite length algorithms terminate. But suppose I start listing out ...
Sidharth Ghoshal's user avatar
-2 votes
1 answer
1k views

How to distinguish the properties applicable to Rice's theorem? [closed]

This is a question that arose when studying Rice's theorem. As you all might know, Rice's theorem (informally and simply) states: "There is no Turing machine (i.e. program) that can always (or ...
Seyed Mohammad's user avatar
11 votes
0 answers
131 views

s-t connectivity on infinite planar graphs with finite description

I would like to know if the following problem is known and has been studied: Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, ...
Marzio De Biasi's user avatar
2 votes
2 answers
180 views

Recommendations for References on undecidability of First Order Logic

I am currently reading Computability and Logic by Boolos Burgess Geoffrey for the proof on "undecidability of first order logic". however, I find the notations a bit confusing. Can anyone recommend ...
GermanShepherd's user avatar
5 votes
1 answer
177 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
Joey Eremondi's user avatar
12 votes
1 answer
880 views

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

What is the simplest computational model for which the emptiness problem is undecidable? Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, ...
Abuzer Yakaryilmaz's user avatar
19 votes
2 answers
505 views

Problems with efficient solution except for a small fraction of inputs

The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it. The halting problem is ...
Jim Graber's user avatar
1 vote
2 answers
224 views

research on systematically attacking multiple instances of undecidable problems

this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint. there are at least ...
vzn's user avatar
  • 11k
2 votes
0 answers
79 views

Regaining decidability by adding axioms that model real world situation

It is known that first order logic is too general to be decidable. Adding axioms with special meaning (e.g. expressing notions such as necessity/obligation, provability, etc.) leads us to modal logics ...
TomR's user avatar
  • 409
13 votes
1 answer
432 views

Good reference about approximate methods for solving logic problems

It is known that many logic problems (e.g. satisfiability problems of several modal logics) are not decidable. There are also many undecidable problems in algorithm theory, e.g. in combinatorial ...
TomR's user avatar
  • 409
9 votes
2 answers
487 views

Is meta-undecidability possible?

There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc. In this case I wonder whether a problem can be meta-undecidable. This means (at least in my ...
Trylks's user avatar
  • 604
3 votes
1 answer
224 views

Decidability in Extensional Type Theory

What are the ways in which one can add a decidable equivalence relation in a type system with undecidable type checking/extensional equality?
AnaK's user avatar
  • 203
11 votes
0 answers
3k views

Eliminate ambiguity from CFG

CFG here stands for context-free grammar. I understand that: Deciding whether a CFG $G$ is ambiguous is undecidable. Deciding whether a CFL $L$ is inherently ambiguous is undecidable. My question ...
Cyker's user avatar
  • 779
17 votes
3 answers
2k views

Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)

Answer: not known. The questions asked are natural, open, and apparently difficult; the question now is a community wiki. Overview The question seeks to divide languages belonging to the complexity ...