# Tagged Questions

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} ...
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 ...
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 ...
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 ...
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 ...
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. ...
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.?
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 ...
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 ...