New answers tagged

1

We start with $f_2(n)$. We have two cases: Case 1: There are arbitrarily long sequences of consecutive $7$'s in $\pi$, then $f(n)=1, \forall n$, and this is clearly computable. Case 2: There is a longest sequence of length $k$ of consecutive $7$'s somewhere in $\pi$ and $k$ is fixed. Hence, $$ f_2(n)=\left\{\begin{array}{ll} 1, & \text{if } n \leq ...


0

No, its not. Consider the function $f$ with $f(e)=1$ if the Turing pgm with index (Gödel number) $e$ stops, and $f(e)=0$ otherwise. This is the halting problem and its undecidable. Thus the function $f$ is not computable.


2

Yes, everything is basically additive. However, there's a slight catch: Suppose $A$ is $\Sigma^0_1$ and $B$ has the form $$\{x: \exists y\varphi(x,y)\},$$ where $\varphi$ is a formula with only bounded quantifiers in which $A$ gets used as a unary predicate symbol. Now there are two plausible guesses for the complexity of $B$, namely $\Sigma^0_1$ (since ...


1

Well, I don't think this is an answer, I have a lot of doubts about it, I would make a comment, but it is too large. I will share some thoughts about this expanding in the direction you are thinking. I don't understand fully the topic, so I would like to know if more people agree with the following. I will use $K$ for this complexity you mentioned and $C$ ...


0

I don't know why you insist that $(n,x)$ not be defined when it doesn't take the value $1$. I prefer to think of it as a total function that takes the value $0$ when $\forall y_1 \le x, \exists y_2 T(n,y_1,y_2)$ is not true, i.e. when $\exists y_1 \le x, \forall y_2, \neg T(n,y_1,y_2)$. Then the question is whether the set of $x$ for which $(n,x)$ maps to $1$...


1

Your argument that $A$ is an index set is not correct: you haven't used anything particular about $y$, so your argument would imply that $$\{p: \phi_y(p)=x\}$$ would be an index set for every choice of $y$. But that's clearly incorrect: for example, take $x=1$ and let $\phi_y(p)=1$ if $p=0$ and $0$ otherwise. By the padding lemma, this is not an index set. ...


0

There is a way to visualize in an algebraic manner the recursive operator of the Primitive Recursive Function class: the Natural Numbers Object (NNO) in the context of a cartesian (or even monoidal) category. It allows to define Primitive Recursion by showing the relations diagramatically. You can see an extensive definition and characterizations in ncatlab....


3

The key fact here is that if a set $A$ qualifies for some level of the hierarchy, then so does any set m-reducible to $A.$ Thus if $A$ is $\Sigma_n$ complete, and also qualifies for some lower level, then any $\Sigma_n$ set also qualifies for that lower level and the hierarchy collapses. To prove the key fact based on your definition for the levels of the ...


3

There are three different notions here: Being $\Sigma_8$. Being properly $\Sigma_8$, which is to say being $\Sigma_8$ but not $\Sigma_n$ for any $n<8$ (or $\Pi_k$ either for that matter for any $k\le 8$). Being $\Sigma_8$-complete. If we want to show that something is $\Sigma_8$-complete, it is - as you say - not enough to simply show that it is $\...


1

The point is that we can "substitute $f$ in" since $f$ itself is total computable: given a computable relation $R$ and a total computable function $f$, the relation $$T(a,b,c):= R(f(a),b,c)$$ is again total computable.


2

Let $\psi$ be a recursive function (no need for partial recursive, because is just the projection function) such that: $\psi(x,y) = x$. By the parameter theorem (S-m-n theorem), there exist a recursive function $f$ such that: $$\phi_ {f(x)}(y) = \psi(x,y) = x.$$ As $f$ is recursive, by the fix-point theorem, it has a fix-point $e$, i.e. $\phi_{f(e)} = \phi_e$...


6

Yes, they are probabilistic in nature. As quoted from wikipedia: Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" ...


0

Feel free to correct/criticize/improve this answer. Alright, I think I got it, at least most of it. I think the S-m-n theorem (for $m=n=1$) can be used to prove the existence of Gödel universal functions. From what I understand, $U(x,y)$, $\varphi_x(y)$, $[\![ x ]\!](y)$ are various notations for the same thing, so I'll use them interchangeably. Let $U$ be ...


3

It's not step $5$, but step $6$. Or more precisely (as Andreas Blass comments below), it's the implicit "step $5.5$" which is needed to make sense of step $6$: computing $f(n)$ in the first place. The issue is that there is no "universal compiler" for primitive recursive functions which is itself primitive recursive. The issue, ...


3

If I understand your idea correctly, you're not actually defining $\mathbb{Z}$ in $\mathbb{Q}$. You're defining $\mathbb{Z}$ in a structure $\tilde{\mathbb{Q}}$, which intuitively consists of $\mathbb{Q}$ together with the details of its construction via ordered pairs of integers. This is unavoidable when you try to check whether $a\vert b$ in a rational $q=(...


1

k becomes computable by excluded middle. Since: $$S = \{n \in \mathbb{N} \mid \text{there are $n$ consecutive 9's in $\pi$}\}.$$ is either bounded or unbounded. For more details see Andrej Bauer here.


1

It is conjectured that $\pi$ is a normal number, which would imply that your function $k(n)$ is computable; since there would always exist a sequence of $n$ consecutive $9$'s in the digits of $\pi$; in particular, it would never take the value $0$ and be non-decreasing. Since very little progress has been made on this conjecture, I believe we don't have an ...


0

By definition of Turing equivalence, we have to study the complexity of saying $W_x\le_T K$ and $K\le_T W_x$. Since we know that $K$ is $\Sigma^0_1$-complete, it is enough to check whether $K\le_T W_x$ (the complexity would not change if you check both). If we write $\varphi_e^A$ for the $e$-th computable function with oracle $A$ and identify a set with its ...


1

Your intuition is correct: if your function was computable, then you would be able to decide the TOTAL problem (deciding whether or not a Turing machine halts on all inputs) - which is undecidable. We first fix an encoding of Turing Machines. We use the following reduction: suppose that you have a machine $M$ that computes $f$. Now, we design a machine $N$, ...


Top 50 recent answers are included