72

The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not. The standard choice for the class $\mathcal{C}$ is statements about ...


30

The correct version of the claim states that every computable language is accepted by infinitely many Turing machines. Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. Let $T_n$ be $T$ together with $n$ unreachable states. Then $T_n$ also accepts $L$, and the machines $T_n$ are all different from one another.


29

On top of what everyone else has said, it may be worth talking about where some of the boundaries of decidability and undecidability are. For natural numbers: The first-order theory of natural numbers with only addition (Presburger arithmetic) is decidable. The first-order theory of natural numbers with only multiplication (Skolem arithmetic) is decidable. ...


20

Your intuition sounds wrong to me. It's not surprising you couldn't prove it, because it isn't true. Roughly speaking, it is possible to find a computer that can simulate all other computers. A universal Turing machine can simulate any other Turing machine, and can be used to simulate any other program in any Turing-complete language. Thus, there is a ...


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

Intuitively? Do you know programming? Can you think of a way of making infinitely many versions of the same program? Say, adding a function foo that you never call creates a different program, but it still does the same thing.


12

The key is quantifiers, both in the theorem, and in the "mathematical statements." First, the theorem says that "there is no algorithm that can take in an arbitrary mathematical statement and prove if it is true or false." This does not mean that, for every mathematical statement, a computer can't determine if it's true or false. It just ...


11

No. Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.


8

Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example: Definition: A function $f : \mathbf{X} \to \mathbf{Y}$ is continuous, if there is a computable partial function $F :\subseteq \mathbf{X} \times \mathbb{N}^\mathbb{N} \...


8

Arno's answer provides some very useful background reading material, I would just like to address your specific question about $\mathbb{R}$. Let us first recall a result by Peter Hertling, see Theorem 4.1 in A Real Number Structure that is Effectively Categorical (PDF here), about computable structure of the real numbers. Suppose we have a representation of $...


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


7

We can have sets $A, B, C$ with linear-time computable maps $f : A \to C$ and $g : B \to C$ such that there exists a map $h : A \to B$ with $f = g \circ h$, but the needed time complexity/Turing degree for $h$ is as high as you want. Proof: Pick a map $H : \Sigma^* \to \Sigma^*$ which is hard in whatever sense you have chosen. Now let $A = C = \Sigma^*$, ...


7

The statement is overly broad, as well as being overly complimentary to people. Computers can’t solve all problems but neither can people. Not sure why the extra drama was added. What that is referring to is basically an aspect of the Halting Problem. A Turing machine can determine the answer to some questions but is unable to do so for others. They even ...


6

Note that the quoted sentence should be "R. This is the empty set, since every $\text{L(M)}$ has an infinite number of TMs that accept it." The other answers are correct, and there are other ways to prove that every language that is accepted by some TM, is actually accepted by $\aleph_0$ distinct TMs. However, following the last sentence in the ...


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

The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input: x ← 0 for i from 1 to A(n,n): x ← x + 1 return x This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time. A better ...


5

There are no catches. Diagonalization is a very general proof technique that works in classical, constructive and computable setting. It is used to prove: that there is no surjection from a set to its powerset that the real numbers cannot be enumerated that the computable real numbers cannot be computably enumerated that the Halting oracle does not exist ...


5

Just put a for loop in there. It goes around n times before doing the calculation. There is no limit to the size of n.


5

Fix a value of $n$. For $b \in \{0,1\}^n$, consider the following algorithm $A_b$: If $x \leq n$ then output $b_x$, otherwise output $0$. Clearly one of the $2^n$ algorithms of the form $A_b$ computes your function $h$, hence $h$ is computable.


5

A simple example of undecidable mathematical statements are whether multivariate integer polynomials have natural roots. This means that we an expression $E(n_0,\ldots,n_k)$ built from natural number constants, natural number variables $n_0,\ldots,n_k$, addition, substraction and multiplication. We then want to know whether a solution for $E(n_0,\ldots,n_k) =...


5

What you're misunderstanding is how "problem" is used in computer science. "Problem" does not refer to finding the correct output for a particular input, but writing an algorithm that returns the correct output for all inputs. For instance, is there an algorithm that sorts a list in linear time? You could write a program that simply goes ...


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

If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability: Proposition: Multiplication by 3 is not computable relative to the decimal representation. Proof: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. ...


4

Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range. For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{...


4

The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general: Deciding ...


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


4

This shouldn't come as a surprise, but you should definitely be familiar with algorithms and datastructures as well as complexity theory. Two fundamental text books are downloadable for free, and you can probably find the answer to your question there: Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal ...


4

Usually, when we talk about the complement of a set we have some reference set to compare to. In the setting of languages over some alphabet $\Sigma$, this means that the complement of some language $L$ would be $\overline L = \Sigma^\ast \setminus L$, i.e. the set of all strings over $\Sigma$ which are not in $L$. In the particular case of $$\mathrm{Sat} = \...


4

No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.


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