2
votes
1answer
157 views

Why should we accept the existence of subsets $A$ such that neither $A$ nor $A^c$ are recursively ennumerable? And how can we persuade others?

Encode every pair $(t,x)$ (where $t$ is a Turing machine and $x$ is an input string) as a distinct natural number. Then the halting subset $H$ fails to be recursive. $$H := \{(t,x) \in \mathbb{N} ...
2
votes
1answer
68 views

Turing degrees of models of ZFC and naming big numbers

Before asking my question, let me give some motivation which could help getting better answers. In this MO question, Scott Aaronson was trying to use the concept of "definable number" to create ...
14
votes
3answers
287 views

Mathematical Notation and its importance

You can see how mathematical notation evolved during the last centuries here. I think everyone here knows that a bad notation can change an otherwise elementar problem into a difficult problem. Just ...
26
votes
4answers
723 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
6
votes
4answers
252 views

What is the relationship between “recursive” or “recursively enumerable” sets and the concept of recursion?

I understand that "recursive" sets are those that can be completely decided by an algorithm, while "recursively enumerable" sets can be listed by an algorithm (but not necessarily decided). I am ...
-1
votes
4answers
264 views

will computers replace (most) mathematicians? [closed]

We already have computers doing proofs and assisting mathematicians with generating proofs. I would expect that their presence will only grow larger with time as the algorithms become more practical. ...
2
votes
2answers
115 views

Complements of recursively enumerable subsets.

Let $A,B \subseteq \mathbb{N}$. If $A$ and $B$ are recursively enumerable, can we say anything about expressions like $A^c \cup B$, $A^c \cap B$, etc.?
4
votes
4answers
295 views

Examples of partial functions outside recursive function theory?

My math background is very narrow. I've mostly read logic, recursive function theory, and set theory. In recursive function theory one studies partial functions on the set of natural numbers. Are ...
1
vote
1answer
176 views

Formal statement of theorem about perfect numbers?

I cannot seem to find the formal statement of the theorem if there are infinite perfect numbers in Wikipedia or online. I searched this site but the closest is the generalization of perfect numbers ...
2
votes
3answers
165 views

“direct” ways in which a non-computable number is used?

I was wondering whether non-computable numbers are ever of "direct" use ? I understand they are immensely useful indirectly, because we need them to do analysis in the real numbers for instance. ...
7
votes
4answers
356 views

Are the computable reals finitary?

In the comment thread of an answer, I said: The computable numbers are based on the intuitionistic continuum, and are not finitary. To which T.. replied: Computable numbers are not based on ...