57

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist? [notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$] ...


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. ...


39

For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are extensionally equal if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output ...


37

For a rather simple version of dependent type theory, Gilles Dowek gave a proof of undecidability of typability in a non-empty context: Gilles Dowek, The undecidability of typability in the $\lambda\Pi$-calculus Which can be found here. First let me clarify what is proven in that paper: he shows that in a dependent calculus without annotations on the ...


21

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable. A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we ...


20

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context. Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (...


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 ...


19

The halting problem is solvable for any Turing machine which uses a known bounded amount of space, by a generalization of the argument given by Yonatan N. If the amount of space is $S$, the alphabet size is $A$, and the number of states is $Q$, then the number of possible configurations is $QSA^S$. If the machine halts then it must halt within $QSA^S$ steps, ...


19

In your edit, you write: What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you ...


19

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO. In other words, $\emptyset$ is decidable. You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides ...


18

Yes. You don't need the excluded middle to derive a contradiction. In particular, diagonalisation still works. Here is a typical diagonalisation argument by Conor McBride. This particular diagonalisation is about incompleteness, not undecidability, but the idea is the same. The important point to notice is that the contradiction he derives is not of the ...


17

(1.1) Is it undecidable whether an arbitrary Turing machine(TM) has 15 states? No, this is a decidable problem. Given a TM in a suitable encoding, it is fairly straightforward to determine how many states the TM has. Consider any common encoding, or define a reasonable one yourself, and then describe an algorithm that answers the question using the encoding....


17

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of such problems (where $\phi_n$ is the $n$-th partial computable function and $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ is the $n$-th ...


17

Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive the empty word is with the single rule $S_0\to \epsilon$ (where $S_0$ is the initial variable, which cannot be derived from other variables). Thus, any other ...


15

Consider the following language: $$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$ $L_2$ is undecidable and not semi-decidable, and same is true of its complement. Why? The intuition is "$M_2$ doesn't halt on input $x_2$" isn't semi-decidable, so $L_2$ is not semi-decidable; and when you look at ...


14

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet. Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-valid" computations of a TM can be coded as strings of a CFG. This is Lemma 8.7 of Introduction to Automata Theory by Hopcroft and Ullman. The authors refer for ...


14

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ uses $H$ to determine if $M(\langle M\rangle)$ halts and, if so, $Q$ loops; otherwise, $Q$ halts. Now, $Q(\langle Q\rangle)$ halts if, and only ...


14

The language $\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$ is not an index set, that is it is not of the form $\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$ for some set of (partial recursive) functions $P$, with $f_M$ the (partial) function computed by TM $M$. Rice's theorem ...


13

Consider the following hint: If $M$ is a TM, and it is given an input of length $12$ (for example), but you only allow $M$ to operate for $10$ steps, what can it do with the input?


13

One useful tool is Rice's theorem. Here is what it says: Let $\emptyset \subsetneq P \subsetneq \mathcal{P}$ a non-trivial set of partially computable unary functions and $\varphi$ a Gödel numbering of $\mathcal{P}$. Then the index set of $P$ $\qquad I_P = \{ i \in \mathbb{N} \mid \varphi_i \in P \}$ is not recursive. You find it also ...


13

This is a common misconception: complexity is not a measure of size. That is, it's not that "bigger" language are harder. Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide. ...


13

No. Quantum computers cannot solve undecidable problems. A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation. However, we already know that if a problem has no classical solution, then it must not have a quantum solution either. ...


12

Here is my approach: I'll show that if you can decide your problem, then you can decide Post's correspondence problem (PCP), which is known to be not decidable. Remember, PCP is a decision problem that asks if in a set of $2$-tuples $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ you can build a sequence (incl. repetition) such that the concatenated $x_i$s and the ...


11

Traditionally, in computability theory all problems are encoded in terms of numbers, or sometimes strings of bits $0$ and $1$. This is a very "low level" kind of thing, it is like programming directly in machine code. The reason for doing this is mostly historic. Gödel originally encode first-order logic in terms of numbers to prove his incompleteness ...


11

Are all undecidable problems recursively enumerable languages? No. See my answer to your third question. If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable? Yes. In particular, recursive (decidable) languages are a subset of the recursively enumerable languages, so anything that's ...


11

Self application is not a necessary ingredient of the proof In a nutshell If there is a Turing machine $H$ that solves the halting problem, then from that machine we can build another Turing machine $L$ with a halting behavior (halting characteristic function) that cannot be the halting behavior of any Turing machine. The paradox built on the self applied ...


10

Hint: Suppose it was. Let $L$ be a recognizable language and let $\overline{L}$ be its complement. If $\overline{L}$ was recognizable as well, let $M_1$ and $M_2$ be recognizers of $L$ and $\overline{L}$, respectively. Can you now use $M_1$ and $M_2$ to construct a decider for $L$? What does this mean for undecidable and recognizable problems like the ...


10

You seem stuck with a logical problem. From the fact that there are books that you cannot read, you cannot infer that you cannot read any book. Saying that the halting problem is undecidable for Turing Machines (TM) only means that there are machines for which there is no way to determine whether they halt or not by some uniform procedure that will always ...


10

Major edit of my original: A naive reading of your question seems to be, let $P$ be the problem $P=$ Given a language, $L$, is it decidable? Then you ask Is $P$ decidable? As D.W. and David have noted, the answer is, "yes it is", though we don't know which of the two trivial deciders is the right one. In order to frame your problem so that it's ...


10

There is some (somewhat scattered) research into the undecidability of the N-body problem from physics (in line with general study of undecidable phenomena in classical and quantum physics), which asks about calculating future trajectories or orbits of objects all subject to $n^2$ gravitational interactions; it has been studied for centuries including by e.g....


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