Skip to main content
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 ...
Pseudonym's user avatar
  • 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 ...
gnasher729's user avatar
  • 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, ...
Jean Abou Samra's user avatar
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 ...
Steven's user avatar
  • 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 ...
benrg's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Steven's user avatar
  • 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 ...
yeputons's user avatar
  • 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 ...
Knogger's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
John L.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
John L.'s user avatar
  • 39.1k
3 votes

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

Lets look at a sample program ...
QuadmasterXLII's user avatar
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 ...
Glenn Willen's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Hendrik Jan's user avatar
  • 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.
vonbrand's user avatar
  • 14.1k
2 votes

How to determine whether this language is regular?

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 ...
Steven's user avatar
  • 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 ...
nir shahar's user avatar
  • 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 ...
John L.'s user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
John L.'s user avatar
  • 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 ...
rici's user avatar
  • 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.
nir shahar's user avatar
  • 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 ...
Nathaniel's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 - ...
Cort Ammon's user avatar
  • 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 ...
Hendrik Jan's user avatar
  • 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 ...
Knogger's user avatar
  • 1,292

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