Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with Search options user 683

Questions related to computability theory, a.k.a. recursion theory

5
votes
You are looking for the recursion theorem. Let $F(e)$ be the function that on input $0x$ returns $P(x)$ and on input $1x$ returns $e$. A fixed point $\varphi_e = \varphi_{F(e)}$ is what you're looking …
answered Apr 16 '14 by Yuval Filmus
2
votes
Hint: Such sets $A,B$ (sans the requirement of recursive enumerability) are called recursively inseparable. According to Wikipedia "it is possible for $A$ and $B$ to be recursively inseparable, disjoi …
answered Dec 25 '14 by Yuval Filmus
13
votes
There are several ways of defining what it means for the Mandelbrot set to be computable. One possible definition is the Blum–Shub–Smale model. In this model, real computation is modelled by a machine …
answered May 18 '15 by Yuval Filmus
3
votes
You can easily use diagonalization to construct a computable real which is not of this form. Fix some enumeration of all triplets $(b,p,q)$. I will describe a process that generates binary digits of a …
answered May 6 '15 by Yuval Filmus
2
votes
You can check that P halts iff $x = ty$ for some integer $t \geq 1$. Hence $g(x,y,z)$ is just the following function: $$ g(x,y,z) = \begin{cases} 1 & \text{ if $x = ty$ for some integer $t \geq 1$}, \ …
answered Apr 24 '18 by Yuval Filmus
3
votes
The basic observation is $$ \begin{align*} A^c &= (A^c \cap B^c) \cup (A^c \cap B) \\ &= (A \cup B)^c \cup (B \cap (A^c \cup B^c)) \\ &= (A \cup B)^c \cup (B \cap (A \cap B)^c). \end{align*} $$ Using …
answered Oct 4 '18 by Yuval Filmus
35
votes
There is no such thing as "the fastest growing function". In fact, there is even no sequence of fastest growing functions. This was already shown by Hausdorff. Given two functions $f,g\colon \mathbb{N …
answered Sep 22 '12 by Yuval Filmus
2
votes
First of all, encoding is up to you — you get to decide the answer to the question you state. Let's consider a more generic situation, in which you want to serialize (convert to bits) a sequence of v …
answered Mar 23 '17 by Yuval Filmus
3
votes
Suppose $f$ is a fixpoint of $A$. First, $$ f(0) = f(1) = f(2) = f(3) = 3f(3), $$ and so $f(0) = f(1) = f(2) = f(3) = 0$. Second, $$ f(5) = 5f(4) = 5f(5), $$ and so $f(4) = f(5) = 0$. Third, if $n = 4 …
answered Jan 8 '13 by Yuval Filmus
5
votes
In one word: no. It doesn't follow logically. It is also definitely not the case that no infinite co-r.e. language can have infinite recursive subsets: every infinite recursive set, say $0^*$, is also …
answered Nov 11 '14 by Yuval Filmus
2
votes
Consider the set $S$ consisting of everything, and the partially computable function $f$ which on input $n$ simulates the $n$th Turing machine, returning whatever the machine outputs (if it ever halts …
answered Sep 27 '17 by Yuval Filmus
5
votes
Your question is a bit unclear, but you're probably looking for this example: $$ A(x,n) = \begin{cases} x & \text{ if program $x$ halts within $n$ steps}, \\ \bot & \text{ otherwise}. \end{cases} $$ T …
answered Apr 12 '18 by Yuval Filmus
5
votes
Let's prove a more general result using diagonalization. Suppose $L_1, L_2, \ldots$ is a countably infinite list of infinite languages. Then there is an infinite language $L$ that doesn't contain any …
answered Nov 24 '14 by Yuval Filmus
0
votes
The predicate $R(x,y,z)$ states that "$M$ accepts the input $x,y$ within $z$ steps". It is computable since we can simulate a given machine on a given input for a bounded number of steps.
answered Sep 8 by Yuval Filmus
4
votes
Since neither HALT nor UC is computable, the machine $M_{UC}$ actually does not exist. The proof by contradiction assumes that HALT is computable and then constructs a machine $M_{UC}$, which contradi …
answered Jun 19 '14 by Yuval Filmus

15 30 50 per page