139
There are only two possibilities to consider.
For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$. In this case, the algorithm that always returns 1 is always correct.
There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$. In this case the following algorithm (with the ...
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$]
...
37
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 ...
36
Fundamental misunderstanding:
Every property of a computer program is non-computable
That is not what Rice's theorem talks about. It talks about properties of functions and that the set of programs computing this function is not decidable. Formally, given $\emptyset \subset P \subset \mathsf{RE}$ the set
$\qquad \displaystyle \{ \langle M \rangle \mid ...
36
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 ...
26
I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem.
Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x_1,...,x_k)$ such that $n \in S$ only if there exists integer coefficients $x_1$,..,$x_k$ such that $f(n;x_1,...,x_k) = 0$. In particular, the halting problem ...
24
Since you wanted "strings", I mention the classic one: Post Correspondence Problem.
21
Yes, let $H$ be binary encoding of the halting problem and $A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$, $B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$, then $AB=\{0,1\}^{\ast}$ (why?)
21
There are many examples but here are a few:
The set of true sentences in the language of arithmetic is undecidable.
The set of provable sentences in set theory (ZFC) is undecidable.
The set of Diophantine equations which have solutions is undecidable.
21
Let's consider the more general problem of machines which stop after at most $N$ steps, for some $N \geqslant 1$. (The following is a substantial simplifcation of a previous version of this answer, but is effectively equivalent.)
As swegi remarks in an earlier response, if the machine stops after at most $N$ steps, then only the cells $0,1,\ldots,N-1$ on ...
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 ...
19
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 (...
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
Any problem that requires only examining a finite amount of data is decidable, because there is an algorithm that consists of enumerating all the potential solutions. It may be ridiculously slow, but that's not relevant: if there is an algorithm, it's decidable.
The problem you state assumes a finite graph, which strongly hints that it's decidable. Strictly ...
answered Mar 9 '12 at 11:19
Gilles 'SO- stop being evil'
37.7k7 gold badges101 silver badges166 bronze badges
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 ...
18
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, ...
16
(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....
15
Just posting a slight elaboration on JeffE's answer.
We know that two functions/cases exist that can compute the function f(n):
A function that always returns true (for all n, there exist n number of consecutive 0's)
A function that will return true if n is smaller than an integer N, where N is defined as the maximum length of consecutive 0's that exist ...
15
Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia...
Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?
Given two CFGs, do they generate the same language?
Given two CFGs, can the first generate all strings that the ...
15
The problem is trivially decidable, as pointed out by Gilles in a comment. As for your other question...
are most problems and algorithms decidable except a few (which is provided here)?
Nope. Actually, most problems are undecidable. In fact, there are uncountably many problems (languages), but there are only countable many Turing Machines, which means ...
15
Yes, there is a need for $L$ to be infinite in order to be undecidable.
To add up on the answers of Raphael and Sam, you should think about "decidable" as things that a computer-program can solve. The program required is very simple, it just needs to output "Yes" for elements in $L$, or otherwise, say no.
So the more "complex" $L$ is, the longer the ...
15
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 ...
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
A general theorem that partially covers the example given is that any $\Sigma^0_1$-hard property of the machine will be undecidable. The halting problem is $m$-reducible to the state-reachability problem, so that shows the state reducibility problem is $\Sigma^0_1$-hard.
However, this is not an "if and only if" theorem like Rice's theorem. If every $\Sigma^...
14
$L_{M_1}$ is in $R$ simply because the number of machine descriptions smaller than a given machine description is finite and any finite language is in $R$.
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 ...
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
Can a quantum computer (theoretically) do things a classical computer (literally) can't? [duplicate]
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.
...
13
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
