Tagged Questions

160 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} ...
72 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 ...
313 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 ...
757 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 ...
265 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 ...
116 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.?
307 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 ...
178 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 ...