# Tagged Questions

computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence ...

335 views

### Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions? This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
86 views

250 views

### Nontrivial, partially uncomputable function

is there any example of function which is computable on some set and uncomputable on other set? That is for example function f(n) which is computable on some (finite, or for example for even numbers) ...
190 views

### A computability-theoretic preorder on reals

My question is about a fairly artificial preorder on functions from $\omega$ to $\omega$, which for simplicity I'll call "reals." For $r, s\in {}^\omega\omega$, write $r\le_E^*s$ if for each real $f$ ...
516 views

### What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?

Let me begin with an example. Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...
123 views

### About infinite subset of halting probability and 1-random set

Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is ...
631 views

### Game of Chess and axiomatic systems [closed]

Consider a deterministic, perfect information, abstract strategy, finite game , with absurdly large state space, say ...chess Q1 Is the game translatable to an axiomatic system? Q2 Can all ...
393 views

### Random infinite sequence : Can machines generate truly random sequences. [closed]

Test : "A True Random Sequence Source and a computer producing a certain sequence of numbers are kept in separate rooms and judges try to tell them apart by conducting a series of tests on the ...
778 views

144 views

### Question about undecidable consequences of Con, learnability and arithmetical complexity of logical consequence

Let$\:$ $T=\{\varphi \in \Pi_1: PA+Con(PA) \vdash \varphi\:\:and\:\: PA\nvdash \varphi \}$. $\:$By the facts presented here Are undecidable consequences of Con recursively enumerable? by Andreas ...
583 views

### What can be done with computability logic that previous logic systems can't?

I've been reading a lot about computability logic lately and I'm superficially aware that it unifies classical, intuitionistic and linear logics. What I'm seeking to know is: Can computability logic ...
270 views

### Computability complexity of the first-order theory of arithmetic?

Hello, It's well known that Kleene's O is $\Pi^1_1$-complete. Does the same thing go for the first-order theory of arithmetic? (I'm talking specifically without set quantifiers---the theory of ...
2k views

### Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

Assume for this question that ZF set theory is sound. Now consider the language "PROVELOOP," which consists of all descriptions of Turing machines M, for which there exists a ZF proof that M runs ...
1k views

### Lawvere's fixed point theorem and the Recursion Theorem

Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, \forall e\exists k[\Phi_e\text{ is total }\implies \Phi_{\Phi_e(k)...
### Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?
Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...