The 2024 Developer Survey results are live! See the results

# Questions tagged [undecidability]

The tag has no usage guidance.

40 questions
Filter by
Sorted by
Tagged with
248 views

• 10.9k
221 views

1 vote
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 "...
• 113
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,596
897 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 ...
362 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. ...
• 284
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,763
425 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 ...
• 13.1k
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.
• 421
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 ...
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 ...
132 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, ...
185 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 ...
179 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 ...
• 2,942
888 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, ...
• 3,707
507 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 ...
• 357
1 vote
225 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 ...
• 11.1k
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 ...
• 409
437 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 ...
• 409
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 ...
• 604
225 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?
• 203
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 ...