Skip to main content

# Tag Info

## Hot answers tagged decidability

12 votes

### What are the conditions necessary for a programming language to have no undefined behavior?

First off, let's be clear on what "undefined behaviour" is. In just C alone (and this is the understanding inherited by C++), there are two possible meanings, depending on which version of ...
• 22.3k
8 votes

### What are the conditions necessary for a programming language to have no undefined behavior?

The C language may say "if you do X, then whatever the result is, is not a violation of the C Standard". "Whatever the result is" can include the result that you hoped for, some ...
• 30.5k
8 votes
Accepted

### Is the Turing machine the only framework to analyse limits of computation?

Turing machines are far from being the only model of computation considered by computer scientists. Among well-studied models of computation are: Turing machines, λ-calculus (and its many variants, ...
5 votes

### Is it possible to determine if a 0-arity function [a program with no input] will always terminate

No, given any program-input pair $(T,x)$ (formally a Turing machine and a word in $\Sigma^*$ for some alphabet $\Sigma$) you can construct a Turing machine with no input that first writes down $x$ and ...
• 29.5k
5 votes
Accepted

### What are the conditions necessary for a programming language to have no undefined behavior?

The problem of statically detecting undefined behavior has nothing to do with undefinedness as such. It's just impossible to prove in general that programs in a Turing-complete language will do ...
• 2,157
4 votes

### Effectively decidable vs. noneffectively (or ineffectively) decidable

"Decidable" and "effectively decidable" mean the same thing. I realize that's a bit confusing; but it reflects a difference in terminology between two communities. (Strictly ...
• 162k
4 votes
Accepted

### Why REC languages is undecidable under emptiness and finiteness?

To decide whether a language is empty you'd have to run $M$ on all possible input strings and verify that $M$ always rejects. How are you going to do that in a way that ensures that your algorithm ...
• 29.5k
4 votes

### What are the conditions necessary for a programming language to have no undefined behavior?

So my question now is, what conditions need to be imposed on a Turing complete language in order to guarantee that all possible programs written in the language will have fully defined behavior ...
• 256
4 votes

### Why get this P=NP? What I am doing wrong?

Both $\texttt{P}$ and $\texttt{NP}$ are subsets of the recursive function $\texttt{R}$, so by definition all $\texttt{NP}$ problems must be decidable by DTMs. But that doesn't make them equal. The ...
• 1,292
3 votes
Accepted

### Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Here is the idea in a nutshell: Given a Turing machine $M$, we can construct a context-free grammar $G$ such that if $M$ halts then $\overline{L(G)} = \{t\}$, where $t$ is the transcript of the ...
• 278k
3 votes
Accepted

### Language of Turing machines that go through some configuration infinitely many times on empty input

No, $L$ is not decidable. Summary (a complete proof for experienced readers): Given a Turing-machine $T$, we can construct algorithmically Turing-machine U that simulates $T$. Moreover, $U$ will ...
• 39.1k
3 votes
Accepted

### Are there any formal systems or programming languages in which its only possible to define functions that have inverses?

Yes, there are. See reversible computing. You could of course design a programming language that only allows using reversible operations (e.g., Toffoli gates), though I'm skeptical whether this ...
• 162k
3 votes
Accepted

### For any two languages A and B there exists J such that both A and B are Turing reducible to J

I don't think this proposition can be proved using the hierarchy of languages as illustrated in the question alone. That hierarchy of languages is too coarse to imply directly any implication between ...
• 39.1k
3 votes

### What are the conditions necessary for a programming language to have no undefined behavior?

Lets look at a sample program ...
3 votes

### What are the conditions necessary for a programming language to have no undefined behavior?

Starting from the C/C++ languages, ruling out all undefined behavior would be very hard. But if you're designing a language from scratch, it's not difficult at all to rule out undefined behavior. Many ...
• 131
2 votes
Accepted

### Regularity of CFG and DCFL

Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class. Regularity of the language ...
• 278k
2 votes

### Regularity of CFG and DCFL

Structurally the classes CFL and DCFL have very different closure properties. CFL are closed under union, but not under complement. DCFL are not closed under union, but closed under complement. The ...
• 30.8k
2 votes
Accepted

### Why finiteness problem of CFL is decidable?

The language generated by a grammar with no useless symbols/productions is finite if and only if there is no non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$. This is easy to check.
• 14.1k
2 votes

For $x = (x_1, \dots, x_n) \in \{0,1\}^n$, define $C_x = \{ w \in \Sigma^* \mid \forall i=1,\dots,n, \;\; \#_{\sigma_i}(w) \equiv x_i \pmod{2} \}$. Notice that the collection $\mathcal{C} = \{C_x \mid ... • 29.5k 2 votes Accepted ### Can 3-SAT be recognized in less than exponential time? This problem stays an open problem (at least using the intuitive definition of "recognizable in poly time" - either running in poly time or looping forever). Consider there is such a TM that ... • 11.6k 2 votes Accepted ### A language of natural numbers is decidable iff it is either finite or the image of some strictly increasing computable function "If$L$is the image of some strictly increasing computable function there's a 1-1 correspondence between the natural numbers and the words in$L$". This is a key observation. You might have ... • 39.1k 2 votes Accepted ### Useless states in a PDA Your formulation of the language is wrong. Your language is a collection of pushdown automata. A PDA$M$is in your language if it has no useless states. This means that for every state$q$, there is ... • 278k 2 votes Accepted ### If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable? There is no definitive answer. If predicate$P$is partially-decidable,$\neg P$can be decidable, partially-decidable or undecidable. Let$P(n)$be "is$n>1$?".$P$is partially ... • 39.1k 2 votes ### Decidability of a context free Grammar "Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with ... • 12.1k 2 votes ### Is the infinite union of decidable languages decidable? Your intuition is right. Hint: for any$x$, the language$\{x\}$is decidable. Think how we can use this fact to construct an undecidable language. • 11.6k 2 votes ### Why there can't be two instances of a "reverse" program in the Halting problem? The main point of the halting problem is that you are running programs on deterministic machines, that means that the execution is always the same. Given a program and an input, it either halts or it ... • 15.8k 2 votes Accepted ### can a model of computation with infinitely many states be nontrivially decidable? A one-counter automaton is a finite-state machine that is augmented with a single counter. The finite-state machine can issue a command to increment or decrement the count, or to test whether the ... • 162k 2 votes ### can a model of computation with infinitely many states be nontrivially decidable? If you want a really interesting logic to work with, take a look at Description Logics. They're an astonishingly large fragment of first order logic. They have three major components: Individuals - ... • 3,351 2 votes Accepted ### Is the following language decidable? Part of my struggle is understanding what the angled brackets around M1/M2 mean in this context. Indeed, you are correct. The question is: given two Turing machines$M_1,M_2$can we decide whether ... • 30.8k 2 votes ### Decidability of {M | M accepts some x in less than |x| steps} Rice's theorem doesn't apply because your language isn't semantic. Let's call your language$L$, and assume that both$M_1$and$M_2$accept$\Sigma^*$for some input alphabet$\Sigma$.$M_1\$ directly ...
• 1,292

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