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

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

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 what $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][2], i.e "mathematical questions that are ultimately about finite processes" which don't include the likes of "CH, AC, the existence of large cardinals".


  [1]: http://www.scottaaronson.com/writings/bignumbers.html
  [2]: http://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver