Skip to main content
added 4 characters in body
Source Link
Ariel
  • 13.6k
  • 1
  • 21
  • 39

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\le n$$< n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_n}$$0.\hat{r_1}...\hat{r_{2^n-1}}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\le n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_n}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $< n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_{2^n-1}}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.

added 51 characters in body
Source Link
Ariel
  • 13.6k
  • 1
  • 21
  • 39

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ iffif the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\le n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_n}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$ (the. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$).

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ iff the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\le n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_n}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$ (the key point is that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$).

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\le n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_n}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.

Source Link
Ariel
  • 13.6k
  • 1
  • 21
  • 39

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ iff the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\le n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_n}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$ (the key point is that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$).