New answers tagged computability
3
votes
Accepted
What's an Example of an Invertible Incomputable Function?
You don't need a concrete example to prove this. Here a simple counting argument suffices: the number of invertible functions $\mathbb N\to \mathbb N$ is uncountable, whereas the number of computable ...
- 61.2k
2
votes
Accepted
Turing Machine to Generate the Sequence 10110111011110... of increasing number of symbols
Let me answer question 2 of yours with a Turing machine that hopefully works. The notation $A/B,C$ means you see an $A$, replace it with $B$ and move to the right if $C=R$ or left if $C=L$.
What this ...
- 1,922
2
votes
Using primitive recursion for defining a function of one argument
There are different conventions, sometimes the case $k = 1$ is treated with a separate definition where $f(0) = c$ for some constant, and sometimes we indeed consider functions with $k = 0$ (nullary ...
- 2,714
1
vote
Accepted
Why is the Turing Jump Baire Class 1?
If $\varphi_n^x(n)\downarrow$, then there is some finite initial segment $\sigma$ of $x$ (the use of the computation) such that for all $y$ extending $\sigma$ we have $\varphi^y_n(n)\downarrow$ as ...
- 251k
9
votes
Accepted
Is the set of all non-computable numbers closed under addition?
The set of non-computable numbers is not closed under addition. Take some non-computable number $a$. Then $1-a$ and $1+a$ are also non-computable, but their sum is 2, a computable number.
- 402
1
vote
Getting from DFAs to regular expressions by solving a system
Let me use capital letters for languages and lower case letters for words and $1$ for the empty word. Let also use $+$ for the union, since we are working in the semiring of languages. Consider the ...
- 41.4k
0
votes
Can 3SAT karp reduces to Direct Hamiltonian Cycle remove buffer/extra node?
Label the variable row nodes left to right $1,2,3,4,\ldots$ and say $1$ and $2$ are allocated to Clause $A$ and $3$ and $4$ are allocated to clause $B$. Say clause $A$ has the variable negated, so ...
- 61.2k
2
votes
Accepted
If SubsetSum can be solved in pseudopolynomial time, can we karp reduce SAT/3SAT to it and solve in pseudopolynomial time?
There's no difference between SAT and 3-SAT here. The crux is that encoding numbers in unary doesn't change the input encoding of SAT or 3-SAT since the inputs aren't numerical, so there's no ...
- 61.2k
1
vote
Accepted
Can the consistency of a complete recursively axiomatizable be decided?
The answer to your question as stated is no.
Fix a sentence $\psi$ which axiomatizes a complete consistent theory. Let $p$ be an arbitrary program. Let $$T_p=\{\psi\}\cup\{\bigwedge_{i=1}^n\lnot \psi\...
- 80.3k
0
votes
Accepted
Probabilistic Kleene's recursión theorem
The answer is positive if my calculations are right. However it depends on the measure. First, let's rephrase the question in a more standard way.
If $X_1, X_2, X_3, \dots$ is a sequence of $\mathbb ...
- 696
4
votes
Accepted
Is there significance to the "smallest possible value for the busy beaver"
Any reasonable proof system will prove a given halting Turing machine halts, just by "following the computation line by line". A danger is that maybe it will incorrectly prove that a non-...
- 61.2k
3
votes
Understanding Church's proof there is no effectively computable algorithm to decide if two lambda expressions are convertable
$\mathfrak{e}(1)$ has a normal form because it is specified to be calculating $E(1)$, which is defined to be either $1$ or $2$, depending on the behavior of $\{A_1\}(1)$.
$\mathfrak{e}$ cannot be ...
- 4,343
3
votes
Difference between bounded and unbounded mu operator?
Yes, the difference is just whether there is a given upper bound. Let $P(x)$ be a predicate on natural numbers:
with the unbounded $\mu$ operator, $(\mu x, P(x))$ is the smallest $x$ such that $P(x)$ ...
- 166
2
votes
Accepted
Are there any links between descriptive set theory and computational complexity theory?
Sure! Here's a whole book about it.
- 1,765
-1
votes
Question about the example correctness of polynomial time reducibility
Ok. I looked up the definition in Sipser. More mathematically, $A \subseteq \Sigma^*$ and $B \subseteq \Sigma^*$ and $\Sigma = \{1,0\}$.
A polynomial-time reduction from $A$ to $B$ is defined
If ...
2
votes
Accepted
Question about the example correctness of polynomial time reducibility
In the context of reduction functions, the implied domain (and codomain) is usually $\Sigma^*$. Assuming that $\Sigma = \{0, 1\}$ (i.e. assuming that we're not dealing with some larger alphabet that ...
- 2,765
2
votes
Accepted
Question about proving Karp Reduction Transitive
I don't understand what you're saying in the last paragraph, so let me just explain the solution in more detail.
What they're saying is that the output size $|f(x)|$ of a poly-time function $f$ scales ...
- 61.2k
Top 50 recent answers are included