An experimental uncertainty implied by failure of the physical Church-Turing thesis
Amir Leshem
In this paper we prove that given a black box assumed to generate bits of a given non-recursive real $\Omega$ there is no computable decision procedure generating sequences of decisions such that if the output is indeed $\Omega$ the process eventually accepts the hypothesis while if the output is different than $\Omega$ than the procedure will eventually reject the hypothesis from a certain point on. Our decision concept does not require full certainty regarding the correctness of the decision at any point, thus better represents the validation process of physical theories. The theorem has strong implications on the falsifiability of physical theories entailing the failure of the physical Church Turing thesis. Finally we show that our decision process enables to decide whether the mean of an i.i.d. sequence of reals belongs to a specific $\Delta_2$ set of integers. This significantly strengthens the effective version of the Cover-Koplowitz theorem, beyond computable sequences of reals.
CT_thesis.tex
%\documentclass[showpacs,preprintnumbers,amsmath,amssymb]{revtex4}
\documentclass[showpacs,amsmath,amssymb,10pt,twocolumn,prl]{revtex4}

% Some other (several out of many) possibilities
%\documentclass[preprint,aps]{revtex4}
%\documentclass[preprint,aps,draft]{revtex4}
%\documentclass[preprint,showpacs,preprintnumbers,prl,10pt,twocolumn,amsmath,amssymb]{revtex4}% Physical Review B

\usepackage{graphicx}% Include figure files
\usepackage{dcolumn}% Align table columns on decimal point
\usepackage{bm}% bold math
\usepackage{epsfig}

%\usepackage{amssymb}
%\usepackage{amsmath}
%\usepackage[super]{natbib}
%\markboth{}{}

\newcommand{\ghat}{\mbox{$\bm \hat g$}}
\newcommand{\Nhat}{\mbox{$\bm {\hat N}$}}
\newcommand{\Nlow}{\mbox{${N_{\hbox{\tiny low}}}$}}
\newcommand{\Nhigh}{\mbox{${N_{\hbox{\tiny high}}}$}}
\newcommand{\Nmax}{\mbox{${N_{\hbox{\tiny max}}}$}}
\newcommand{\Iul}{\mbox{${I_{\hbox{\tiny ul}}}$}}
\newcommand{\Idl}{\mbox{${I_{\hbox{\tiny dl}}}$}}


% abbreviations for bold english letters (vectors)
\newcommand{\va}{\mbox{${\bf a}$}}
\newcommand{\vah}{\mbox{${\bf \hat a}$}}
\newcommand{\vat}{\mbox{${\bf \tilde a}$}}
\newcommand{\vb}{\mbox{${\bf b}$}}
\newcommand{\vd}{\mbox{${\bf d}$}}
\newcommand{\rh}{\mbox{${\hat r}$}}

\newcommand{\vx}{\mbox{${\bf x}$}}
\newcommand{\vxt}{\mbox{${\bf \tilde x}$}}
\newcommand{\vh}{\mbox{${\bf h}$}}
\newcommand{\htld}{\mbox{${\tilde h}$}}
\newcommand{\vhh}{\mbox{${\bf \hat h}$}}
\newcommand{\hhat}{\mbox{${\hat h}$}}
\newcommand{\ve}{\mbox{${\bf e}$}}
\newcommand{\vg}{\mbox{${\bf g}$}}
\newcommand{\vgh}{\mbox{${\bf \hat g}$}}
\newcommand{\vq}{\mbox{${\bf q}$}}
\newcommand{\vt}{\mbox{${\bf t}$}}
\newcommand{\vw}{\mbox{${\bf w}$}}
\newcommand{\vdw}{\mbox{${\bf dw}$}}

\newcommand{\vwh}{\mbox{${\bf \hat w}$}}
\newcommand{\wh}{\mbox{${\hat w}$}}
\newcommand{\vwt}{\mbox{${\bf \tilde w}$}}
\newcommand{\wt}{\mbox{${\tilde w}$}}
\newcommand{\vs}{\mbox{${\bf s}$}}
\newcommand{\vsh}{\mbox{${\bf \hat s}$}}
\newcommand{\vst}{\mbox{${\bf \tilde s}$}}
%\newcommand{\vr}{\mbox{${\bf r}$}}
\newcommand{\vv}{\mbox{${\bf v}$}}
\newcommand{\vu}{\mbox{${\bf u}$}}
\newcommand{\vy}{\mbox{${\bf y}$}}
\newcommand{\vz}{\mbox{${\bf z}$}}
\newcommand{\vn}{\mbox{${\bf n}$}}
\newcommand{\vnt}{\mbox{${\bf \tilde n}$}}
\newcommand{\ntld}{\mbox{${\tilde n}$}}
\newcommand{\nhat}{\mbox{${\hat n}$}}
\newcommand{\phat}{\mbox{${\hat p}$}}
\newcommand{\vzero}{\mbox{${\bf 0}$}}
\newcommand{\vone}{\mbox{${\bf 1}$}}

% abbreviations for matrices
\newcommand{\mA}{\hbox{{\bf A}}}
\newcommand{\mAh}{\mbox{${\bf \hat A}$}}
\newcommand{\mAt}{\mbox{$\bf \tilde A$}}
\newcommand{\mB}{\hbox{{\bf B}}}
\newcommand{\mBh}{\mbox{${\bf \hat B}$}}
\newcommand{\mC}{\hbox{{\bf C}}}
\newcommand{\mCh}{\mbox{${\bf \hat C}$}}
\newcommand{\mD}{\hbox{{\bf D}}}
\newcommand{\mDt}{\mbox{$\bf \tilde D$}}
\newcommand{\mE}{\hbox{{\bf E}}}
\newcommand{\mG}{\hbox{{\bf G}}}
\newcommand{\mF}{\hbox{{\bf F}}}
\newcommand{\mH}{\hbox{{\bf H}}}
\newcommand{\mHb}{\mbox{${\bf \bar H}$}}
\newcommand{\mHt}{\mbox{${\bf \tilde H}$}}
\newcommand{\mI}{\hbox{{\bf I}}}
\newcommand{\mIh}{\mbox{${\bf \hat I}$}}
\newcommand{\mN}{\hbox{{\bf N}}}
\newcommand{\mM}{\hbox{{\bf M}}}
\newcommand{\mMh}{\mbox{{$\bf \hat M$}}}
\newcommand{\mP}{\hbox{{\bf P}}}
\newcommand{\mQ}{\hbox{{\bf Q}}}
\newcommand{\mR}{\mbox{{$\bf R$}}}
\newcommand{\mRh}{\mbox{{$\bf \hat R$}}}
\newcommand{\mRt}{\mbox{{$\bf \tilde R$}}}
\newcommand{\mS}{\mbox{{$\bf S$}}}
\newcommand{\mSb}{\mbox{{$\bf \bar S$}}}
\newcommand{\mSh}{\mbox{{$\bf \hat S$}}}
\newcommand{\mSt}{\mbox{{$\bf \tilde S$}}}
\newcommand{\mT}{\mbox{{$\bf T$}}}
\newcommand{\mU}{\mbox{{$\bf U$}}}
\newcommand{\mUh}{\mbox{{$\bf \hat U$}}}
\newcommand{\mV}{\mbox{{$\bf V$}}}
\newcommand{\mVh}{\mbox{{$\bf \hat V$}}}
\newcommand{\mW}{\hbox{{\bf W}}}
\newcommand{\mWh}{\mbox{${\bf \hat W}$}}
\newcommand{\mWt}{\mbox{${\bf \tilde W}$}}
\newcommand{\mX}{\mbox{{$\bf X$}}}
\newcommand{\mY}{\mbox{{$\bf Y$}}}
\newcommand{\mZ}{\mbox{{$\bf Z$}}}



%abbreviations for greek letters

\newcommand{\ga}{\alpha}
\newcommand{\gb}{\beta}
\newcommand{\grg}{\gamma}
\newcommand{\gd}{\delta}
\newcommand{\gre}{\varepsilon}
\newcommand{\gep}{\epsilon}
\newcommand{\gz}{\zeta}
\newcommand{\gzh}{\mbox{$ \hat \zeta$}}
\newcommand{\gh}{\eta}
\newcommand{\gth}{\theta}
\newcommand{\gi}{iota}
\newcommand{\gk}{\kappa}
\newcommand{\gl}{\lambda}
\newcommand{\gm}{\mu}
\newcommand{\gmh}{\hat \mu}
\newcommand{\gn}{\nu}
\newcommand{\gx}{\xi}
\newcommand{\gp}{\pi}
\newcommand{\gph}{\phi}
\newcommand{\gr}{\rho}
\newcommand{\gs}{\sigma}
\newcommand{\gsh}{\hat \sigma}
\newcommand{\gt}{\tau}
\newcommand{\gu}{\upsilon}
\newcommand{\gf}{\varphi}
\newcommand{\gc}{\chi}
\newcommand{\go}{\omega}

%Uppercase Greek

\newcommand{\gG}{\Gamma}
\newcommand{\gD}{\Delta}
\newcommand{\gTh}{\Theta}
\newcommand{\gL}{\Lambda}
\newcommand{\gX}{\Xi}
\newcommand{\gP}{\Pi}
\newcommand{\gS}{\Sigma}
\newcommand{\gU}{\Upsilon}
\newcommand{\gF}{\Phi}
\newcommand{\gO}{\Omega}

%Uppercase bold Greek

\def\bm#1{\mbox{\boldmath $#1$}}
\newcommand{\vga}{\mbox{$\bm \alpha$}}
\newcommand{\vgb}{\mbox{$\bm \beta$}}
\newcommand{\vgd}{\mbox{$\bm \delta$}}
\newcommand{\vge}{\mbox{$\bm \epsilon$}}
\newcommand{\vgl}{\mbox{$\bm \lambda$}}
\newcommand{\vgr}{\mbox{$\bm \rho$}}
\newcommand{\vgrh}{\mbox{$\bm \hat \rho$}}
\newcommand{\vgrt}{\mbox{$\bm {\tilde \rho}$}}

\newcommand{\vgt}{\mbox{$\bm \gt$}}
\newcommand{\vgn}{\mbox{$\bm \gn$}}
\newcommand{\vgth}{\mbox{$\bm {\hat \tau}$}}
\newcommand{\vgtt}{\mbox{$\bm {\tilde \tau}$}}
\newcommand{\vpsi}{\mbox{$\bm \psi$}}
\newcommand{\vphi}{\mbox{$\bm \phi$}}
\newcommand{\vxi}{\mbox{$\bm \xi$}}
\newcommand{\vth}{\mbox{$\bm \theta$}}
\newcommand{\vthh}{\mbox{$\bm {\hat \theta}$}}

\newcommand{\mgG}{\mbox{$\bm \Gamma$}}
\newcommand{\mgGh}{\mbox{$\hat {\bm \Gamma}$}}
\newcommand{\mgD}{\mbox{$\bm \Delta$}}
\newcommand{\mgDone}{\mbox{$\bm \Delta^{(1)}$}}
\newcommand{\mgDtwo}{\mbox{$\bm \Delta^{(2)}$}}

\newcommand{\mgU}{\mbox{$\bm \Upsilon$}}
\newcommand{\mgL}{\mbox{$\bm \Lambda$}}
\newcommand{\mPsi}{\mbox{$\bm \Psi$}}
\newcommand{\mgX}{\mbox{$\bm \Xi$}}
\newcommand{\mgS}{\mbox{$\bm \Sigma$}}

%Abbreviatians for blackboard bold
\newcommand{\oA}{{\mathbb A}}
\newcommand{\oC}{{\mathbb C}}
\newcommand{\oF}{{\mathbb F}}
\newcommand{\oN}{{\mathbb N}}
\newcommand{\oP}{{\mathbb P}}
\newcommand{\oQ}{{\mathbb Q}}
\newcommand{\oR}{{\mathbb R}}
\newcommand{\oZ}{{\mathbb Z}}

%Abbreviatians for caligraphic letters

\newcommand{\Nu}{{\cal V}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cH}{{\cal H}}
\newcommand{\cK}{{\cal K}}
\newcommand{\cI}{{\cal I}}
\newcommand{\cL}{{\cal L}}
\newcommand{\cM}{{\cal M}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cO}{{\cal O}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cU}{{\cal U}}
\newcommand{\cV}{{\cal V}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cX}{{\cal X}}

\newcommand{\barx}{{\bar x}}
\newcommand{\bargs}{{{\bar \gs}^2}}


%\newcommand{\rH}{^{ \raisebox{1pt}{$\rm \scriptscriptstyle H$}}}
\newcommand{\rH}{^{*}}
\newcommand{\rT}{^{ \raisebox{1.2pt}{$\rm \scriptstyle T$}}}
\newcommand{\rF}{_{ \raisebox{-1pt}{$\rm \scriptstyle F$}}}
\newcommand{\rE}{{\rm E}}
%\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
%[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{principle}[theorem]{Principle}
\newtheorem{prop}{Proposition}[section]
\newtheorem{claim}[theorem]{Claim}

%\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
%\theoremstyle{remark}
\newtheorem{question}{Question}[section]
\newtheorem{coro}{Corollary}[section]

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{array}}
\newcommand{\ena}{\end{array}}
%\newcommand{\bds}{\begin {description}}
%\newcommand{\eds}{\end {description}}
\newcommand{\bds}{\begin {itemize}}
\newcommand{\eds}{\end {itemize}}
\newcommand{\bdf}{\begin{definition}}
\newcommand{\blm}{\begin{lemma}}
\newcommand{\edf}{\end{definition}}
\newcommand{\elm}{\end{lemma}}
\newcommand{\bthm}{\begin{theorem}}
\newcommand{\ethm}{\end{theorem}}
\newcommand{\bprp}{\begin{prop}}
\newcommand{\eprp}{\end{prop}}
\newcommand{\bcl}{\begin{claim}}
\newcommand{\ecl}{\end{claim}}
\newcommand{\bcr}{\begin{coro}}
\newcommand{\ecr}{\end{coro}}
\newcommand{\bquest}{\begin{question}}
\newcommand{\equest}{\end{question}}

%Abbreviatians for other symbols
\newcommand{\rarrow}{{\rightarrow}}
\newcommand{\Rarrow}{{\Rightarrow}}
\newcommand{\larrow}{{\leftarrow}}
\newcommand{\Larrow}{{\Leftarrow}}
\newcommand{\restrict}{{\upharpoonright}}
\newcommand{\nin}{{\not \in}}





%\newcommand{\ha}{\mbox{$\hat{\b{a}}$}}
%\newcommand{\tba}{\mbox{$\tilde{\b{a}}$}}
%\newcommand{\yh}{\mbox{${\hat y}$}}
%\newcommand{\vth}{\mbox{${\boldsymbol {\theta}}$}}
%\newcommand{\ups}{\mbox{${\Upsilon}$}}
%\newcommand{\vthh}{\mbox{${\boldsymbol {\hat \theta}}$}}
%\newcommand{\vtht}{\mbox{${\boldsymbol {\tilde \theta}}$}}
%\newcommand{\veps}{\mbox{${\underline \epsilon}$}}
%\newcommand{\vrho}{\mbox{${\boldsymbol {\rho}}$}}
%\newcommand{\vrhoh}{\mbox{${\boldsymbol {\hat \rho}}$}}
%\newcommand{\vrhot}{\mbox{${\boldsymbol {\tilde \rho}}$}}

%\newcommand{\vy}{\mbox{${\bf y}$}}
%\newcommand{\vyh}{\mbox{${\bf \check y}$}}
%\newcommand{\vyht}{\mbox{${\bf \hat y}$}}
%\newcommand{\vnh}{\mbox{${\bf \check n}$}}
%\newcommand{\omn}{\mbox{${\om_{_N}}$}}
%\newcommand{\pikon}{\mbox{${\frac{2\pi k}{N}}$}}



% Abrreviations
\newcommand{\ie}{\hbox{i.e.}}
\newcommand{\eg}{\hbox{e.g.}}
\newcommand{\Pnx}{\mbox{$P_{\hbox{next}}$}}
\newcommand{\Knx}{\mbox{$K_{\hbox{next}}$}}

\newcommand{\round}{\hbox{round}}


\newcommand{\bbT}{{\mathbb T}}
\newcommand{\bbN}{{\mathbb N}}
\newcommand{\bone}{{\mathbf{1}}}
\newcommand{\Cfield}{{\mathbb C}}
\newcommand{\calG}{{\mathbb{G}}}
\newcommand{\calS}{{\mathcal{S}}}
\newcommand{\bLambda}{{\boldsymbol \Lambda}}
\newcommand{\bv}{\mbox{${\mathbf v}$}}
\newcommand{\by}{\mbox{${\mathbf y}$}}
\newcommand{\bs}{{\mathbf{s}}}
\newcommand{\bA}{\mbox{${\mathbf A}$}}
\newcommand{\bB}{\mbox{${\mathbf B}$}}
\newcommand{\vgL}{{\boldsymbol \Lambda}}
\newcommand{\qref}[1]{(\ref{#1})}  %nos formules
\newcommand{\valpha}{{\boldsymbol \alpha}}

\newcommand{\var}{\mbox{var}}

%\nofiles
%\renewcommand{\baselinestretch}{1.5}

\begin{document}
%

%\preprint{APS/MPML-001}
\title{An experimental uncertainty implied by failure of the physical
 Church-Turing thesis}
\author{Amir Leshem}
\affiliation{School of Engineering, Bar-Ilan university,\\ 52900,
Ramat-Gan, Israel}
\homepage{http://www.eng.biu.ac.il/~leshema} 
\date{\today}% It is always \today, today,
             %  but any date may be explicitly specified
\begin{abstract}
In this paper we prove that given a black box assumed to generate bits
of a given non-recursive real $\Omega$  there is no computable decision
procedure generating sequences of decisions such that if the output is
indeed $\Omega$ the process eventually accepts the hypothesis while if the
output is different than $\Omega$ than the procedure will eventually
reject the hypothesis from a certain point on. Our decision concept 
does not require full certainty regarding the correctness of the decision at any point, thus better represents the validation process of physical theories.
The theorem has strong implications on the falsifiability of physical theories entailing the failure of the physical Church Turing thesis. Finally we show that our decision process enables to decide whether the mean of an i.i.d. sequence of reals belongs to a specific $\Delta_2$ set of integers. This significantly strengthens the effective version of the Cover-Koplowitz theorem, beyond computable sequences of reals.
\end{abstract}
\pacs{02.10.A, 03.67.Lx}% PACS, the Physics and Astronomy
                             % Classification Scheme.
%\keywords{Suggested keywords}%Use showkeys class option if keyword
                              %display desired
%\keywords{Church-Turing thesis, Hypothesis testing, experimental uncertainty}
\maketitle
\section{Introduction}
Church-Turing thesis states that every function $f:\bbN \rarrow \bbN$
that is algorithmically computable is recursive or equivalently
computable by a universal Turing machine. This is a mathematical
statement about algorithms not physical computers. 
 This thesis has been supported by the equivalence of all models of 
computations to date, e.g., Turing machines, register machines
and lambda calculus \cite{enderton}. A
stronger thesis termed the physical Church-Turing thesis is that every
finitely realizable physical process can be perfectly simulated by a
universal Turing machine operating by finite means (see \cite{deutsch85}, \cite{penrose90} and the references therein). 
This thesis is much stronger. It has been argued that there might be finitely 
realizable  physical processes that can compute non-computable functions 
 e.g., by analog computation \cite{siegelmann95},  stronger versions of quantum computing \cite{nielsen97},\cite{kieu2003} or general relativity \cite{shagrir2003}. Furthermore  \cite{penrose90,penrose94} claims that 
some of the open problems in physics (e.g., quantum gravitation) and the failure to generate artificial intelligence might have underlying non-computable physical
processes.
Similarly the possibility that some physical constants are non-computable has 
been conjectured. If indeed a physical constant is
non-computable then more and more accurate measurements of the
constant (or repeated independent observations with i.i.d noise) will provide 
us more bits of its binary expansion, therefore
providing an oracle that breaks the physical Church-Turing thesis.  

In this paper we discuss the empirical validation and refutation of the hypothesis 
that a computing device generates a non-computable real number. 
Deutsch \cite{deutsch85} argues that this is 
hopeless since any finite experiment generates a finite sequence of 
measurements with finite precision so the output of any experiment is 
computable. However, following Cover \cite{cover73} we might envision a 
different strategy:  Our null hypothesis is that we are given a black box 
generating the bits of a specific non-computable real
(In order to be able to use the digits provided by the black box we need to 
know what is the assumed outcome, otherwise a random number generator will provide us  almost surely with useless bits of a non-computable real).
We now perform an infinite sequence of tests, each sampling more and 
more bits of the given black box.  This measurement procedure serves as
an oracle, and our task is to refute the null hypothesis if the oracle
is a false oracle. The only requirement we have is that if the oracle
is a false oracle (does not provide the bits of $\gO$) then from a certain 
point our procedure always rejects the null hypothesis, and if it indeed 
provides the bits of $\gO$ then from a certain point on we will always accept 
the hypothesis. This viewpoint is in line with the idea of falsifying a 
physical theory \cite{popper59}. Note that while our decisions are 
asymptotically correct we are
never certain about this fact. Since at any finite stage we might change our
decision, we never get full certainty regarding the null hypothesis, only 
growing confidence. This is 
much like the validation process of physical theories. The theory is accepted 
only if it is sufficiently simple on one hand and has not yet been refuted by 
experiment on the other hand.

Cover \cite{cover73} used this strategy to
verify that a mean of a random sequence is rational. His motivation was to 
provide tests for certain simple representations of well known physical 
constants \cite{wyler71, lenz51, good70}.  While at
every finite stage any confidence interval contains rationals and
irrationals he shows that if the number is rational or is irrational
outside a certain set of measure 0 then with probability one the
sequence of decisions is correct from a certain point on. Koplowitz 
\cite{koplowitz77} and
later Peres and Dembo \cite{peres94} proved that if we want to test a 
hypothesis regarding two sets contained in disjoint $F_{\gs}$ sets then
the correct decision is made with probability one for both $H_1$
and $H_0$ and the set of measure 0 can be assumed empty. 
However in all these papers little attention was paid to
actual computability of the decision procedures. The procedures
are computable only if the countable sequence of reals is a 
computable sequence of computable reals. 

In this paper we apply the same decision concept to testing the
non-computability of physical constants (and actually to any output of
a physical black box) providing us with a sequence of approximations
to a real number. We show that given the output of a black box which is 
assumed to provide us bits of a given non-computable real there is NO decision
procedure (deterministic or probabilistic) that makes an infinite
sequence of decisions such that any false oracle is detected from a
certain point on. The proof is general enough to apply to any physical
model of computation. It means that if the Church-Turing thesis is
true, than there is no way to experimentally refute the hypothesis that 
a finitely realizable process provides us a non-computable number. 
This type of uncertainty requires us to choose between falsifiability of
such a physical prediction (which would be the most substantial prediction of a
theory claiming that a given physical process is non-computable) 
and our belief in the given theory. Hence accepting the failure of the 
physical Church-Turing thesis implies that we need to revise the notion of
experimental refutation of physical theories as proposed by Popper.

On the positive side we provide a computable decision procedure that almost 
surely decides asymptotically whether the mean of an i.i.d random process 
belongs to a given $\gD_2$ non-computable set of natural numbers 
using the asymptotic decision concept.
Our result significantly strengthens Cover's result since 
$\gD_2$ sets cannot be effectively enumerated, and therefore Cover's proof 
fails to provide a computable decision procedure. 

\section{Physical processes, Decision procedures and experiment design}
In this section we review the concept of an experiment and a decision
procedure to falsify a given prediction of a physical theory.
We focus on the experimental evidence that the output of a black
box is a non-computable real. The formulation is sufficiently general to
include statistical decisions as well as deterministic procedures.

First we comment that basically any physical observation is subject to noise 
and finite accuracy limitations. This implies that the best we can hope from 
an experimental devices is to obtain a sequence of measurements with increasing
accuracy rather than a single infinitely accurate measurement. However we do
assume that there is no practical limitation on the observation and that by 
averaging we might reduce effects of observation noise as much as we would 
like (otherwise it would be trivially impossible to decide anything regarding 
non-computability, since any finite sequence is by itself computable). 
Even this assumption ignores some inherent limitations on measurement such as
the fact that certain parameters cannot be simultaneously measured due to 
quantum limitations, or fundamental limitations on synchronization, etc.

We now provide some definitions and notations to be used later in the
paper.
\bdf
\begin{enumerate}
\item For a finite sequence $s=\left<s(0),s(1),...,s(N-1)\right>$ we
denote the length of the sequence by $l(s)=N$.
\item For two sequences $s,t$ where $l(s) \le l(t)$ we denote
$s \le^* t$ if for all $n < l(s)$ we have $s(n)=t(n)$.
\item Let $s$ be a sequence of integers (finite or infinite). Let $n \le
l(s)$ then $s \restrict n=\left<s(0),s(1),...,s(n-1)\right>$.
\item $\go$ is the set of natural numbers and $2^{<\go}$ is the binary tree
of all binary finite sequences. 
\end{enumerate}
\edf

Let $\gO$ be a non-computable real. We shall assume without
loss of generality that our real $\gO$ is the characteristic function
of a non-computable set $W$. 
Suppose that as in figure 1 a black box S, provides us at each
experiment $n=0,1,2,...$ with a bit $S(n)$.  
We would like at each stage $n$ to decide whether the bits provided by
$S$ so far are the initial bits of our real $\gO$ or not. We do not
require that all our decisions are correct, however we require that for any
$S=<S(0),S(1),...>$, if $S \neq \gO$ then from a certain finite
stage we decide correctly that $S \neq \gO$. Similarly if $S=\gO$ then
we do not change our mind regarding this and we accept the null
hypothesis from a certain stage onwards. Note that the decision
procedure can be viewed as a computable function 
$F:2^{<\go} \rarrow \{0,1\}$ where for any $s=<s(0),...,s(N-1)>$ 
\beq
F(s)=0 \hbox{\ iff we decide that $s \not \le^* \gO$}.
\eeq

Let $S$ be a source of bits. We measure the output of $S$. 
A physical theory stating that $S$ generates the
bits of a specific non-recursive real is experimentally falsifiable if
and only if there is a computable decision procedure $F:2^{<\go}
\rarrow \{0,1\}$ such that for every $S$, $ \lim_{n \rarrow \infty} F(S \restrict n)$ exists and 
\beq
\lim_{n \rarrow \infty} F(S \restrict n)=0 \iff S \neq \gO.
\eeq
The setup is presented in figure \ref{experiment}.
\begin{figure}
    \begin{center}
    \mbox{\psfig{figure=figures/decision1.eps,width=0.28\textwidth}}
    \end{center}
    \caption{A general decision process for refuting the null
    hypothesis $S=\gO$}
  \label{experiment}
\end{figure}
We do not require that we know whether $S\neq \gO$ or not at any
finite stage since any decision might be reversed after further observation. 
However we do require that performing more and more measurements of the output 
of $S$ will eventually accept the null
hypothesis 
\beq
H_0: S=\gO
\eeq
if it is valid or reject it from a certain point on  if  $S \neq
\gO$. 
This notion of verification is consistent with the way we test
physical theories in general \cite{popper59}. We do not know at any 
finite stage whether the theory is correct but we require that the theory
is falsifiable, i.e., if the theory is wrong then there is an experiment
falsifying the theory. If the theory is false then from a certain point on our experiments will refute the theory. 


\section{Main theorem}
The asymptotic verification described above 
 can be utilized in all existing physical
theories e.g., verifying that the absolute zero is not achievable. This 
is not the case with non-recursiveness. Our main theorem proves that
the non-recursiveness of the outcome of a finitely realizable physical system
implies a significant
measurement uncertainty in the sense that no experiment can be designed to
eventually refute or accept the prediction of the theory. Interestingly 
theorem \ref{delta2} provides an example of asymptotic decision process 
regarding membership in $\gD_2$ sets. Hence not all is lost regarding 
testing hypotheses about non-recursive sets. 

\bthm
\label{main_theorem}
Let $W$ be a non-recursive set (e.g., the set of G\"{o}del numbers of all 
halting Turing machines). Let $\gO=1_{W}$ be the characteristic
function of $W$. Then there is no computable decision procedure 
$F:2^{< \go} \rarrow \{0,1\}$ such that $\lim_{n \rarrow \infty} F(S \restrict n)$ exisits and  
\beq
\label{asymptotic}
\lim_{n \rarrow \infty} F(S \restrict n)=0 \iff S \neq \gO
\eeq
\ethm 
Proof: Assume towards contradiction that we are given a recursive
$F:2^{< \go} \rarrow \{0,1\}$ such that (\ref{asymptotic}) holds.
\bcl
For every $t$  define 
\[
R_t=\left\{r | t \le^*r \wedge F(r)=1 
\right\}.
\]
If $t \not \le^* \gO$ then $R_t$ is finite.
\ecl
Proof of the claim: Assume that $t \not \le^* \gO$ and 
 $R_t$ is infinite. Define a subtree $T_t$ of $2^{<\go}$ by
\[
T_t=\left\{s | t \le^*s \wedge \exists r \in R_t (s \le^* r) 
\right\}.
\]
This is the subtree spanned by all extensions of $t$ that are decided the
wrong way (since $t \not \le^* \gO$). Since $R_t$ is infinite $T_t$ is
an infinite tree with finite branching. Therefore by K\"{o}nig's lemma it
has an infinite
branch $b$. However for every node $s \le^* b$ there is an extension
$r \in b$ satisfying $F(r)=1$. Therefore 
\[
\lim_{n \rarrow \infty} F(b \restrict n) \neq 0
\] 
contradicting the definition of $F$, since if $S$ generates $b$ either we
asymptotically accept $H_0$, i.e., we decide $b=\gO$, which is false, or we 
change our decision
infinitely many times. This contradicts the definition of $F$ and the claim is 
proved.

We are now in position to finish the proof of theorem \ref{main_theorem}. Let 
$m_0$ be sufficiently large so that $F(\gO \restrict m)=1$ for all $m_0 \le
m$. 
Such an $m_0$ exists since by (\ref{asymptotic}).
By our claim we have 
\[
t \le^* \gO \iff \forall m \left(m_0 \le m \rarrow \exists s \in
2^m(t \le^* s \wedge F(s)=1) \right).
\]
Let $m_1=\max\{n,m_0\}$. Then for all $n$ 
\[
n \in W \iff 
\forall m \left( m_1 \le m \rarrow \exists s \in
2^m(F(s)=1) \wedge s(n)=1 \right).
\]
Similarly for all $n$ 
\[
n \not \in W \iff \forall m \left(m_1 \le m \rarrow 
\exists s \in 2^m(F(s)=1) \wedge s(n)=0 \right).
\]
Since all internal quantifiers are bounded $W$ is both a $\Pi_1$ and 
$\gS_1$ set so it is recursive contradicting our assumption.

\section{Deciding that a mean belongs to a non-computable set}
While in the previous section we proved that even given a deterministic
output of a black box we cannot define a computable sequence of decisions
asymptotically deciding whether the black box provides us the digit of a 
specific non-computable real, we show that certain decisions 
regarding non-computable sets  can be made. The general properties of $\gD_2$ 
sets can be found in \cite{shoenfield}.

\bthm
\label{delta2}
Let $A \subseteq \oN$ be a $\gD_2$ set of natural numbers. Assume $x_1,x_2,...$
is a sequence of i.i.d real random variables with mean $\gm$ and variance 
$\gs^2<\infty$. Then there exist a
recursive decision procedure $F:R^{<\go} \rarrow \{0,1\}$ such that almost surely (with respect to realizations of the sequence) 
\beq
\lim_{n \rarrow \infty} F\left(\left<x_1,...,x_n \right> \right)=1 
\iff \gm \in A
\eeq
\ethm
Note that unlike the Cover Koplowitz theorem we do not require that the set 
$A$ admits a recursive enumeration. This strengthens the effective version of 
the Cover-Koplowitz theorem to $\gD_2$ sets of integers.

Proof: Our decision procedure consists of two steps. We First decide whether 
$\gm$ is an integer based on an approach similar to the Cover-Koplowitz 
theorem using that the set $\oN$ admits a recursive numeration. 
Then we rely on the law of iterated logarithms to obtain an 
estimate of $\gm$ and exploit the definition of $A$ as a $\gD_2$ set.
To test whether $\gm \in \oN$ let 
$
\barx_N= \frac{1}{N} \sum_{n=1}^N x_n \\
$
be the sample mean and let 
%\beq
$\bargs_N=\frac{1}{N} \sum_{n=1}^N (x_n-\barx_N)^2
$
%\eeq
be the sample variance.
Almost surely $\barx_N \rarrow \gm$ and 
$\bargs \rarrow \gs^2$.
Furthermore by the law of iterated logarithms almost surely only finitely many
times
%\beq
$
|\gm-\barx_N|>\sqrt{\frac{\gs^2 \log \log N}{N}}
$
%\eeq
and for every $\gre>0$ almost surely only finitely many times 
\beq
\gs^2>(1+\gre)\bargs_N
\eeq
Fix $\gre>0$.
Let $\gd_N=\sqrt{\frac{(1+\gre)\bargs_N \log \log N}{N}}$
and
%\beq
$
\gmh_N=\round(\barx_N).
$
%\eeq  
If $\gm \in \oN$ then with probability one only finitely many times
$\gmh_N \neq \gm$, and except finitely many times this holds whenever 
%\[
$
|\gmh_N-\barx_N|<\gd_N
$
%\]
If on the other hand $\gm \nin \oN$ then almost surely except finitely many 
$N$'s $|\gm-\gmh_N|>\gd_N$ and therefore almost surely except finitely many 
times
%\[
$
|\gmh_N-\barx_N|>\gd_N
$
%\]
Let $\left<d_n:n=0,1,...\right>$ be a sequence of decisions for the hypothesis
$H^{\oN}_0: \gm \in {\oN}$ given by 
\beq
d_n=\left\{
\bea{ll}
1 & \hbox{if} \ \ |\gmh_n-\barx_n|\le \gd_n \\
0 & \hbox{if} \ \ |\gmh_n-\barx_n|>\gd_n
\ena
\right.
\eeq
By the discussion above almost surely $d_n$ is correct except finitely many 
times. 
If $d_n =0$ decide $\gm \nin A$. Otherwise we assume that $\gm \in \oN$ and 
 almost surely $\gmh_n=\gm$ for all 
but finitely many $n$'s. Hence if $d_n=1$ assume that $\gm_n \in \oN$. 
We now define a procedure for testing whether $\gmh_n \in A$. 
To that end recall that since $A$
is $\gD_2$ there are recursive relations $\phi(m,k,n), \psi(m,k,n)$ such that
\beq
\label{Aformulas}
\bea{lcl}
n \in A &\iff& \exists m \forall k [\phi(m,k,n)] \\
n \nin A &\iff& \exists m \forall k [\psi(m,k,n)] 
\ena
\eeq
\bdf
An $m_0$ such that $\forall k \phi(m_0,k,n)$ is called a witness for 
$n \in A$.
An $m_0$ such that $\forall k \psi(m_0,k,n)$ is called a witness for 
$n \nin A$.
$m_0$ decides $n \in A$ if $m_0$ is a witness for $n \in A$ or for 
$n \nin A$.
\edf
Obviously by (\ref{Aformulas}) for each $n$ either there is a witness 
that $n \in A$ or there is a witness for $n \nin A$. 
Therefore given $n$ and $m$ if we compute 
$\left< \left(\phi(m,k,n),\psi(m,k,n)\right), k=1,2,... \right>$ 
we must obtain some $k$ where either $\phi(m,k,n)$ fails or $\psi(m,k,n)$
fails. Moreover by definition there is a least $m$ where one of the formulas 
holds for all $k$. 

Let $\gmh_N$ be the estimate of $\gm$ given that $d_N=1$.
Let $m_0$ be the minimal $m$ such that only one of the formulas fails for 
some $k$ (assume without loss of generality this is $\phi$). Then with probability one except 
finitely many  $N$'s
\beq
\forall k<N [\phi(m_0,k,\gmh_N)]
\eeq
and for sufficiently large $N$ $m_0$ is the minimal one.
This suggests the following decision procedure:
Assume that we have decided that at stage $N$ that $\gm \in \oN$ ($d_N=1$).
Decide $e_N=1$ if the minimal $m$ such that 
\beq
\forall k<N [\phi(m,k,\gmh_N)]
\eeq
is smaller than the minimal $m$ such that 
\beq
\forall k<N [\psi(m,k,\gmh_N)].
\eeq
By the discussion above, if $\gm \in A$ then $e_N=1$  
except finitely many $N$'s and if $\gm \nin A$, $e_N=0$ 
except finitely many $N$'s. This ends the proof.

Finally we comment that if we replace $\oN$ by any countable recursive sequence
of recursive reals $S=\left<s_n: n \in \oN \right>$
and $A \subseteq \oN$ is $\gD_2$ then we can extend the above result to test 
whether $\gm \in \left<s_n: n \in A \right>$. However similarly to Cover's 
result if the closure of $S$ is uncountable then there is a measure $0$ 
subset of $\oR \backslash S$ on which the test might fail. 

\bibliographystyle{plainnat}
%\bibliography{cover}
\begin{thebibliography}{17}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi
\bibitem[Cover(1973)]{cover73}
T.~M. Cover.
\newblock On determining the irrationality of the mean of a random variable.
\newblock \emph{Annals of Statistics}, 1\penalty0 (5):\penalty0 862--871, 1973.

\bibitem[Deutsch(1985)]{deutsch85}
D.~Deutsch.
\newblock Quantum theory, the {C}hurch-{T}uring principle and the universal
  quantum computer.
\newblock \emph{Proc. R. Soc. Lon. A}, 400:\penalty0 97--117, 1985.

\bibitem[Enderton(1972)]{enderton}
H.~B. Enderton.
\newblock \emph{A Mathematical Introduction to Logic}.
\newblock Academic Press, 1972.

\bibitem[Good(1970)]{good70}
I.~J. Good.
\newblock The proton and neutron masses and a conjecture for the gravitational
  constant.
\newblock \emph{Physical Review Letters}, 33A:\penalty0 383--384, 1970.

\bibitem[Kieu(2003)]{kieu2003}
T.~D. Kieu.
\newblock Quantum algorithm for {H}ilbert's tenth problem.
\newblock \emph{International Journal of Theoretical Physics}, 42\penalty0
  (7):\penalty0 1451--1468, July 2003.

\bibitem[Koplowitz(1977)]{koplowitz77}
J.~Koplowitz.
\newblock In \emph{Abstracts of papers, Int. Symp. on Info. Theory, Ithaca,
  NY}, page~64, 1977.

\bibitem[Lenz(1951)]{lenz51}
F.~Lenz.
\newblock The ratio of proton and electron mass.
\newblock \emph{Physical Review}, 82:\penalty0 554, 1951.

\bibitem[Nielsen(1997)]{nielsen97}
M.~A. Nielsen.
\newblock Computable functions, quantum measurements, and quantum dynamics.
\newblock \emph{Physical Review Letters}, 79\penalty0 (15):\penalty0
  2915--2918, October 1997.

\bibitem[Penrose(1990)]{penrose90}
R.~Penrose.
\newblock \emph{The Emperor's New Mind}.
\newblock Oxford University Press, 1990.

\bibitem[Penrose(1994)]{penrose94}
R.~Penrose.
\newblock \emph{Shadows of the Mind}.
\newblock Oxford University Press, 1994.

\bibitem[Peres and Dembo(1994)]{peres94}
Y.~Peres and A.~Dembo.
\newblock A topological criterion for hypothesis testing.
\newblock \emph{Annals of statistics}, 22\penalty0 (1):\penalty0 106--117,
  1994.

\bibitem[Popper(1959)]{popper59}
K.~R. Popper.
\newblock \emph{The Logic of Scientific Discoveries}.
\newblock Hutchinson, 1959.

\bibitem[Shagrir and Pitowsky(2003)]{shagrir2003}
O.~Shagrir and I.~Pitowsky.
\newblock Physical hypercomputation and the {C}hurch-{T}uring thesis.
\newblock \emph{Minds and Machines}, 13\penalty0 (1):\penalty0 87--101,
  February 2003.

\bibitem[Shoenfield(1971)]{shoenfield}
J.~R. Shoenfield.
\newblock \emph{Degrees of unsolvability}.
\newblock North-Holland, mathematics studies. Elsevier, 1971.

\bibitem[Siegelmann(1995)]{siegelmann95}
H.T. Siegelmann.
\newblock Computation beyond the {T}uring limit.
\newblock \emph{Science}, 268\penalty0 (5210):\penalty0 545--548, April 1995.

\bibitem[Wyler(1971)]{wyler71}
A.~Wyler.
\newblock A mathematicians version of the fine structure constant.
\newblock \emph{Physics Today}, 24:\penalty0 17--19, 1971.

\end{thebibliography}

\end{document}

math-ph0604017.extracted_bib
\begin{thebibliography}{17}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi
\bibitem[Cover(1973)]{cover73}
T.~M. Cover.
\newblock On determining the irrationality of the mean of a random variable.
\newblock \emph{Annals of Statistics}, 1\penalty0 (5):\penalty0 862--871, 1973.

\bibitem[Deutsch(1985)]{deutsch85}
D.~Deutsch.
\newblock Quantum theory, the {C}hurch-{T}uring principle and the universal
  quantum computer.
\newblock \emph{Proc. R. Soc. Lon. A}, 400:\penalty0 97--117, 1985.

\bibitem[Enderton(1972)]{enderton}
H.~B. Enderton.
\newblock \emph{A Mathematical Introduction to Logic}.
\newblock Academic Press, 1972.

\bibitem[Good(1970)]{good70}
I.~J. Good.
\newblock The proton and neutron masses and a conjecture for the gravitational
  constant.
\newblock \emph{Physical Review Letters}, 33A:\penalty0 383--384, 1970.

\bibitem[Kieu(2003)]{kieu2003}
T.~D. Kieu.
\newblock Quantum algorithm for {H}ilbert's tenth problem.
\newblock \emph{International Journal of Theoretical Physics}, 42\penalty0
  (7):\penalty0 1451--1468, July 2003.

\bibitem[Koplowitz(1977)]{koplowitz77}
J.~Koplowitz.
\newblock In \emph{Abstracts of papers, Int. Symp. on Info. Theory, Ithaca,
  NY}, page~64, 1977.

\bibitem[Lenz(1951)]{lenz51}
F.~Lenz.
\newblock The ratio of proton and electron mass.
\newblock \emph{Physical Review}, 82:\penalty0 554, 1951.

\bibitem[Nielsen(1997)]{nielsen97}
M.~A. Nielsen.
\newblock Computable functions, quantum measurements, and quantum dynamics.
\newblock \emph{Physical Review Letters}, 79\penalty0 (15):\penalty0
  2915--2918, October 1997.

\bibitem[Penrose(1990)]{penrose90}
R.~Penrose.
\newblock \emph{The Emperor's New Mind}.
\newblock Oxford University Press, 1990.

\bibitem[Penrose(1994)]{penrose94}
R.~Penrose.
\newblock \emph{Shadows of the Mind}.
\newblock Oxford University Press, 1994.

\bibitem[Peres and Dembo(1994)]{peres94}
Y.~Peres and A.~Dembo.
\newblock A topological criterion for hypothesis testing.
\newblock \emph{Annals of statistics}, 22\penalty0 (1):\penalty0 106--117,
  1994.

\bibitem[Popper(1959)]{popper59}
K.~R. Popper.
\newblock \emph{The Logic of Scientific Discoveries}.
\newblock Hutchinson, 1959.

\bibitem[Shagrir and Pitowsky(2003)]{shagrir2003}
O.~Shagrir and I.~Pitowsky.
\newblock Physical hypercomputation and the {C}hurch-{T}uring thesis.
\newblock \emph{Minds and Machines}, 13\penalty0 (1):\penalty0 87--101,
  February 2003.

\bibitem[Shoenfield(1971)]{shoenfield}
J.~R. Shoenfield.
\newblock \emph{Degrees of unsolvability}.
\newblock North-Holland, mathematics studies. Elsevier, 1971.

\bibitem[Siegelmann(1995)]{siegelmann95}
H.T. Siegelmann.
\newblock Computation beyond the {T}uring limit.
\newblock \emph{Science}, 268\penalty0 (5210):\penalty0 545--548, April 1995.

\bibitem[Wyler(1971)]{wyler71}
A.~Wyler.
\newblock A mathematicians version of the fine structure constant.
\newblock \emph{Physics Today}, 24:\penalty0 17--19, 1971.

\end{thebibliography}