4
$\begingroup$

In reference to 1961 paper "On Non Computable Functions" by T. Rado.

Motivation - Scott Aaronson's Who Can Name the Bigger Number?.

M is an n-state binary Turing machine. A valid BB-n entry is a set $(M,s)$ where M halts in exactly s steps. $E_n$ is the set of all valid BB-n entries. Since one cannot have both $(M,s_1) \in E_n$ and $(M,s_2) \in E_n$ for $s_1\not=s_2$, Rado concludes that $E_n$ is a subset of all possible n-state binary Turing machines which is finite and hence, $E_n$ is an exceptionally well-defined non-empty finite set. He proceeds to prove that some functions defined over $E_n$ are non-computable.

But because I'm aware of the Halting problem, I am unable to satisfactorily answer the following question : does $E_n$ exist? Let s be the number of steps required by M to halt when started on a blank tape.

Question 1. Can I say s does not exist?

If the answer is yes, then I can say (M,s) does not exist, and hence $E_n$ does not exist. If not, what can I say about s?

Question 2. If I do not want $E_n$ to exist, and in general sets that admit non-computable functions over them to exist, would I need to yank this statement : "every subset of a set is a set" out of my intuition? Is there an axiomatic system where everything that exists is computable?

I was a bit surprised about how easily Rado assumed the existence of $E_n$. When you can't even construct a set, it is not surprising that some functions over it are non-computable. I ask this question in the similar vein as Scott Aaronson asks Succinctly naming big numbers: ZFC versus Busy-Beaver, i.e "mathematical questions that are ultimately about finite processes" which don't include the likes of "CH, AC, the existence of large cardinals".

Improve this question
$\endgroup$
5
  • $\begingroup$ You can say (to yourself) whatever pleases you. For Question 1, s exists iff M halts when given a blank tape as input. There are machines that halt on 1 step which have n states, so E_n is nonempty for n large enough (n >0?). That you can't determine its members in your lifetime may be troubling, but so what? There are axiomatic systems where everything that exists are computable, but they are limited in scope. You might ponder more about what is bothering you, and see if you can turn that into a question. Gerhard "Believes No Impossibilities Before Coffee" Paseman, 2011.06.22 $\endgroup$
    – Gerhard Paseman
    Commented Jun 23, 2011 at 0:42
  • $\begingroup$ Gerhard : What bothers me is that I cannot understand the meaning of existence outside of computability. If you could point to an actual weak axiomatic system with its limited scope, I'd be very interested to know some simple statements that cannot be expressed in them, but intuitively, I should be able to. i.e what prompts the bootstrapping of properties that render axiomatic systems victims of Godel's incompleteness theorems. $\endgroup$
    – Saran Neti
    Commented Jun 23, 2011 at 3:11
  • $\begingroup$ @sarannmr: If you do not accept the existence of the non-computable, then you must also reject the existence of uncountable things. Without the uncountable, you do not have the real numbers, only the rationals. This rejection is apparently also a feature of intuitionism (en.wikipedia.org/wiki/Intuitionism). Maybe worth a look? $\endgroup$
    – mhum
    Commented Jun 23, 2011 at 4:16
  • 1
    $\begingroup$ @mhum: that wikipedia article looked like it had problems. One can definitely prove that the power set of the naturals is uncountable in intuitionistic logic. (Notice that "X is uncountable" is a negated sentence, a proposition of the form $q = \neg p$. For such $q$, one has $q$ equivalent to $\neg \neg q$.) $\endgroup$
    – Todd Trimble
    Commented Jun 23, 2011 at 11:47
  • $\begingroup$ @mhum The Wikipedia article on Intuitionism certainly helps. Finitism rejects the existence of countably infinite, Intuitionism rejects the existence of uncountably infinite; I was looking for a constructive theory that accepts the uncountably infinite but rejects the non-computable. But, thanks! $\endgroup$
    – Saran Neti
    Commented Jun 23, 2011 at 16:22

2 Answers 2

Reset to default
11
$\begingroup$

The question of whether a given fixed Turing machine $M$ halts or not is something that can be independent of our fundamental axioms of mathematics.

For example, let $M$ be the Turing machine that searches for a proof of a contradiction from ZFC, say, halting only upon finding one. One could in principle write down the specific instructions for such a machine.

And in a universe in which ZFC is consistent, then $M$ never halts. But by the incompleteness theorem, if ZFC is consistent, then there are universes in which ZFC is true, but Con(ZFC) is false, and in such a universe, $M$ does halt.

Thus, the question of whether $s$ exists for a given machine $M$ that we can write down is something that can be independent of our axioms. And strengthening the theory doesn't really solve the problem, since the same argument will apply to the stronger theory.

More generally, although the collection of $n$-state programs that halt is a finite set, and therefore the halting times of the programs in this set is definitely bounded by some finite number, and we can easily prove that it is bounded, nevertheless the specific lower bounds that we can provide for how long the computations proceed will depend on our background theory.

The situation is that stronger and stronger theories may prove higher and higher lower bounds on the value of how long $n$-state programs can run while still halting. No theory (computably axiomatized consistent) will be able to prove the optimal values for the busy beaver function, since if there were such a theory, then by searching for proofs we would be able to compute those values, which we provably cannot. So the stronger and stronger theories will continually settle additional halting instances pushing the values of the busy beaver function still higher.

So we can easily prove that $E_n$ exists, since it is determined by the set of $n$-state programs that halt and their running times. The thing we sometimes cannot prove is whether a given machine $M$ is in $E_n$ or not. A weak theory may not be able to prove that $M$ halts, even when a stronger theory is able to do so.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Joel Thanks! Your statement "...stronger and stronger theories may prove higher and higher lower bounds..." and mhum's comment that non-countable should be rejected, point to an analogy. In Calculus class, I had a similar problem understanding the $\epsilon$, $\delta$ definition of the limit of a real valued function - which now seems intuitively obvious. Given an $\epsilon > 0$, I should be able to come up with a computably axiomatized theory that proves a lower bound for BB(n) to within that $\epsilon$ $\endgroup$
    – Saran Neti
    Commented Jun 23, 2011 at 16:53
2
$\begingroup$

The issue your raising is the distinction between existence and computability.

The set $E_n$ is uncomputable, but it clearly exists because every machine must either (A) halt or (B) not halt. A machine cannot both halt AND not halt.

An analogous situation would be if I took 10 coins and put them in a box and shook it and proclaimed that $X$ = the number of heads-up coins in the box before I opened the box. Now clearly $X$ exists and is well-defined, but I cannot know it until I open the box (assuming the coins are suitably random).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .