Planned maintenance impacting Stack Overflow and all Stack Exchange sites is scheduled for Monday, September 16, 2024, 5:00 PM-10:00 PM EDT (Monday, September 16, 21:00 UTC- Tuesday, September 17, 2:00 UTC). The email/password authentication method will be unavailable for logging in and registering. Read more here

# Tag Info

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
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

### 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
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

### 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
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