41

Optimized program must have the same behavior as the original program. Consider the following program: int main() { f(); g(); } , where it's guaranteed that $f$ is pure function. The only question is: does it finish its execution? If it does, then we can replace main()'s body with g(). Otherwise, we should replace it with an infinite loop. ...


20

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a ...


10

For most interesting optimisations, I think this is implied by Rice's theorem. For real numbers, Richardson's theorem is also relevant here.


7

Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$. Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this ...


5

Your argument "goes backwards." Note that your definition of $R$ depends on $D$ (step $2$). This means you can't conclude that no machine decides $A_R$, merely that $D$ specifically doesn't. Basically, what you've written looks like this: CLAIM: there is some $x$ such that no $y$ does [task involving $x$]. PROOF: picking some $y$, we build an $x$ such ...


5

One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer. Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i ...


4

It's your second bullet point - something odd in the recursive relationship. The argument is trying to show a contradiction by exhibiting a finite language that is undecidable. In other words, the argument needs to show that there exists a finite language $L$ such that for every decider $D$, there is some input $w$ such that $D$ incorrectly decides whether ...


4

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$. You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always ...


4

Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (...


3

The (non)halting condition for PDAs doesn't make much sense; "non-halting" for a PDA means that there are one or more $\epsilon$-moves (not input read) that can cause a "loop" or an infinite stack expansion. In order to test if a PDA accepts a string $x$, a Turing machine should not "barely simulate" it (i.e. recusively enumerate all reachable (partial ...


3

I don't know, but I suspect it's an open question. If the theory of the reals with exponential function is decidable, then your problem is decidable, too. It is known that if Shanuel's Conjecture holds, then the former is decidable, so your problem is too. If I understand correctly, the following paper tackles your problem: The identity problem for ...


3

No, it is not necessarily recursively enumerable. There are languages that are recursively enumerable but not recursive. Thus, their complement is not recursively enumerable. From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).


3

It might come as a surprise to you, but the language $$L=\{k\in\mathbb N :\text{the binary expansion of} \sqrt2\text{ contains $k$ consecutive $1$s}\}$$ is decidable, even if we could not construct an algorithm that can demonstrate whether the binary expansion of $\sqrt2$ contains $k$ consecutive $1$s or not given arbitrary $k$. As Yonatan N indicated, let ...


3

A language $L \subseteq \{0,1\}^*$ is well-defined if, for each possible word $w \in \{0,1\}^*$, it is clearly specified whether $w$ is in $L$ or not. This means that your rules must cover every case (for every word $w \in \{0,1\}^*$, at least one of your rules specifies whether $w$ is in $L$ or not), and that there are no contradictions (there does not ...


3

Maybe you're confusing two different problems. The algorithm you are describing shows that the problem of testing whether a CFG generates some string from $1^∗$ is decidable (e.g., see here at page 21). Anyway, the problem of testing whether a CFG generates all the strings of the language $1^∗$ is truly decidable. Consider all production rules to be simple (...


3

What you are missing is that if $\langle M, w\rangle \notin \overline{A_{\mathrm{TM}}}$, i.e. if $M$ halts on input $w$, you don't know whether or $M_1 \notin L$. If $M$ does halt on $w$, but this takes longer than $20$ steps, it would also hold that $M_1 \in L$. Thus, you don't have a reduction here. That the language $L$ cannot be co-RE is an immediate ...


3

Let $H$ be the language of all Turing machines that halt on empty input. Clearly $H$ is undecidable. Let $L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$. Clearly $L$ is undecidable. If $L$ were decidable, then a Turing machine $M$ for $L$ would also imply the existence of a Turing machine $M'$ that decides $H$. $M'$ with input $T$ simply ...


3

With some programming languages and computation models, you could even say that optimizing programs is the same as running them — just with a subset of computation rules. Then, if you allow enough optimizations to happen, it is clear that optimization faces the same non-termination problems as running programs. Let me elaborate on my claim by providing a ...


3

Like many undecidability results about program analysis, this is a consequence of Rice's theorem. Consider the function $g := x \mapsto \mathsf{if} \; f(x) \; \mathsf{then} \; 0 \; \mathsf{else} \; x$ where $C$ may contain variables. An optimal optimizer must optimize calls to this function to $0$ if $f(x)$ is true for every $x$. The property “this function ...


3

This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain this remarkable and beautiful argument, from many viewpoints. Still, to answer your question: denote by $Q$ the program you describe. Then $Q$ is a valid ...


3

(For the below, I referred extensively to this github repo as well as private communication with @aozgaa) Languages can be represented as infinite-length bitstrings (ILB). We will use the two interchangeably. We will also represent strings meant to be inputs to TMs as integers, where a 1 bit in position $w$ in an ILB $A$ means that the $w$th string in $\...


3

Let us say that $H$ is a partial Halting oracle if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and: If $H$ terminates and outputs "yes" then $M(x)$ halts. If $H$ terminates and outputs "no" then $M(x)$ does not halt. In particular, $H$ is allowed to run forever and not give an ...


3

The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable. If a Turing machine $T$ is fixed, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$). As an example in which this problem is decidable consider the trivial Turing machine $T$ ...


2

The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question. It makes sense to talk about whether a language is decidable or undecidable. It doesn't make sense to talk about whether a program is decidable or undecidable. If you check the formal definition of decidable, you'll see that ...


2

I and several colleagues answered this question here with a necessary and sufficient criterion for when the language $L_{x=y}$ (all words having an equal number of occurrences of $x,y$) is regular. We also show the same for fewer $x$ than $y$, and more $x$ than $y$.


2

First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the ...


2

Enumerate the c.e. set, keep only entries that appear in increasing lexocographic order. As the c.e. set is infinite, there will be new elements larger than the last kept one (thus the subset is infinite). To decide the subset, enumerate until hitting the element or a larger one.


2

The difference between the models stems, intuitively, from the ability of CFGs to count. More precisely, CFGs are able to generate strings of the form $a^nb^n$, where the number of $a$'s and $b$'s is the same. This ability grants it the power to compare strings, which can then be utilized to show undecidability, because the CFG is able to compare the ...


2

Your summary of the proof of undecidability is not accurate. Your specification of $\overline{A_{TM}}$ is not correct. For a reasonable exposition of the proof, see https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf particularly the beginning of Section 1 and Section 3. The intuition is not easy to convey, as the proof is not entirely ...


2

The phrase Every context-free language is decidable has the following meaning: If the language $L$ is context-free, then $L$ is decidable or in other words If $L$ is a context-free language then $L$ is a decidable language


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