# Tag Info

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