# Tag Info

75

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.

28

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

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.

13

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

8

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

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^*$, ...

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

6

No - even within (say) the class of $\Sigma_1$ (= c.e., r.e., semidecidable, ...) sets, there is lots of non-linearity even up to Turing reducibility (of course this is stronger than non-linearity up to many-one reducibility since $m$-reductions imply $T$-reductions). The study of the c.e. degrees began with Post's problem: is there a c.e. set whose Turing ...

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 ... 5 If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically. Some examples: Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable ... 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. 4 A lot of confusion arises because the sloppy notation and imprecise terminology involving free and bound variables. Let me try to clear some of it up. The title of your question wrongly claims that \forall x \in \mathbb{N} \,.\, \Phi(x,x) is a function, which it is not. It is a truth value. Let us see why this is the case. Suppose someone defined f by ... 3 You're asking two questions, one about computability and one about computational complexity. The usual rule is to ask one question per post. I'll answer the second question. No, under standard conjectures, the computational complexity could be quite bad. Suppose f:A \to C is given by f(x) = \alpha^x \bmod p and g:B \to C is given by g(x) = \beta^x ... 3 For k even, a language L is in \Pi_k if there exists a recursive predicate R such that$$ x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \forall y_{k-1} \exists y_k \, R(x,y_1,\ldots,y_k) $$The quantifiers alternate between \forall and \exists. When k is odd, the same definition works, but the last quantifier is \forall:$$ x \...

3

This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of $$2^{nm}.$$ This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound $$n2^m.$$ ...

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