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

learn more… | top users | synonyms

12
votes
4answers
2k views

Is modern computability theory “really” about algorithms?

Apologies if my question seems overly naive, but I haven't seen/heard/read any good answers. What is modern computability theory "really" about? The study of feasible(even remotely feasible) ...
1
vote
1answer
528 views

final step(s) for a proof that a function is not primitive recursive

My function is $f:\mathbb{N} \rightarrow \mathbb{N},\ f(n)=2\uparrow ^n 3$ , the Ackermann(-Péter) function, with the second argument fixed to 3 (and "$\uparrow$" the Knuth up-arrow), which I believe ...
1
vote
2answers
290 views

How to approximate non-computably recursive set by computably recursive set

let $J=S \cap D $,$G=S \cup D$,sort $G$,$a_n \in G$. Function $\gamma (n,s)=\frac{\Sigma_{a_i \in J}^n a_i^s}{\Sigma_{i=1}^n a_i^s}$. Given S ,a non computably enumerable set,is there a computably ...
0
votes
1answer
155 views

Equivalence of monadic axioms

Call two axioms equivalent if they imply the same set of theorems. I am interested in decidability of so defined equivalence. In this generality the problem is obviously undecidable since it can be ...
3
votes
1answer
579 views

Lower-semicomputable supermartingales with bounded increments

I'm interested in whether Levin and Solomonoff's results on "universal semimeasures" can be extended to other settings. One case that especially interests me is finding "universal" strategies in the ...
5
votes
2answers
452 views

A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size

I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out. I am aware of the probability of a Random program halting on a ...
13
votes
2answers
786 views

Can randomness add computability?

I have been looking at Church's Thesis, which asserts that all intuitively computable functions are recursive. The definition of recursion does not allow for randomness, and some people have suggested ...
11
votes
0answers
507 views

Minimal resources for Undecidability of First-Order Logic: the number of variables

It is well-known that First-Order Logic (FO) with a full vocabulary (i.e., a countable numbers of unary predicate symbols, a countable number of binary predicate symbols, etc.) is undecidable. And it ...
1
vote
1answer
119 views

undecidability in the dynamics of functions $f: \Sigma^* \rightarrow \Sigma^*$

Does anyone know any undecidable problems in the dynamics of functions (not necessarily monoid homomorphisms or anything) from \Sigma^* to \Sigma^* where \Sigma is a finite set? In particular, I'm ...
3
votes
1answer
354 views

Axiomatizations of complete theories

This question was motivated by this recent question by Ricky Demer. In his paper $\Pi^0_1$ classes and Boolean combinations of recursively enumerable sets, Carl Jockusch showed that there is no ...
3
votes
1answer
481 views

computable “completion” of ZFC

Let $f : \omega \to \{\text{wffs of set theory}\}$ be a function. Let $\leq_f$ be a total order on $\omega$. Definition: $\langle f,\leq_f \rangle$ is a computable quasi-completion of ZFC if and ...
12
votes
2answers
899 views

What proofs cannot be relativized

I am afraid this post may show my naivety. At a recent conference, someone told me that there are some arguments in computability theory that don't relativize. Unfortunately, this person (who I ...
20
votes
10answers
3k views

Physics and Church–Turing Thesis

Is there constructed some set of physical laws from which we can logically obtain that any function that can be implemented in some device is Turing computable? EDIT I believe that if we restrict ...
5
votes
1answer
333 views

Enumerating levels of Grzegorczyk-hierarchy

Grzegorczyk has divided the class of primitive recursive functions to Grzegorczyk-hierarchy by their rate of growth. In this hierarchy $E_i\subset E_{i+1}$ and the subset-relation is strict. Also ...
5
votes
2answers
338 views

Consistent r.e. extensions of non r.e. theories.

Let $\mathcal{L}$ be some first-order language, and $T$ be a consistent set of formulas of $\mathcal{L}$ which is not recursively enumerable. Under what conditions will there be $T'\supset T$ such ...
13
votes
2answers
631 views

Are the axioms for higher category-theory effectively computable?

I ask this, although I don't conduct any research in the area, or even plan to. -- There seems to be general agreement that the axioms for higher categories grow very rapidly in complexity as the ...
10
votes
2answers
597 views

Is Robinson Arithmetic biinterpretable with some theory in LST?

Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
2
votes
3answers
394 views

Graph properties: definability and decidability

[This is a side question to Supervenience in mathematics.] There are graph properties that are not FO-definable, but MSO-, TC-, or LFP-definable. There may be other graph properties that are not ...
2
votes
1answer
465 views

Semidecidable sets

A set $S$ (of natural numbers) is (semi)decidable if its (semi)characteristic function is effectively calculable. From a set theoretic point of view, the semicharacteristic function of a set is just ...
3
votes
1answer
447 views

Turing degrees of nonstandard models of PA

Since the theorems of (PA + "there is a nonstandard number") are recursively enumerable, by the Low Basis Theorem, WKL0's proof of the completeness theorem gives a nonstandard model of PA of [low ...
5
votes
1answer
262 views

Recursive Non-Well-Orders that are Sneaky, but not THAT Sneaky.

This is a variant on Sneaky Recursive Non-Well-Orders where it was asked Is there a recursive function $f$ such that whenever $a\in\mathcal{O}$, $f(a)$ is a Turing index for a linear ...
0
votes
1answer
225 views

Is it correct to state that basic primitive recursive functions are in fact combinators?

Is it correct saying that the Zero, Successor and Projection functions can be seen as combinators?
11
votes
2answers
697 views

(un)decidability in matrix groups

Given a collection of matrices $S=\{M_1, \dots, M_k\}$ in (say) $SL(n, Z), \ n>2$ does $S$ generate $SL(n, Z)?$ Similar are questions are undecidable for $n\geq 4$ (eg, given a set $S$ as above, ...
14
votes
7answers
1k views

Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example. Now, in the logic courses (that I have had look ...
9
votes
2answers
709 views

Martin's cone theorem and recursion theory

Martin's remarkable cone theorem in the theory of determinacy says the following: Suppose $A\subseteq \omega^\omega$ is Turing invariant and determined. If $\forall x\exists y(x\le_T y\& y\in ...
8
votes
4answers
1k views

Undecidability in Conway's Game of Life

I strongly believe that - given the rules of Conway's Game of Life and an initial configuration - it is not decidable by a Turing Machine whether a given pattern will emerge, let alone as a stable ...
4
votes
2answers
293 views

How does the Constructibility Degree of a real compare with its Turing Degree?

Specifically, is it the case that (for $a,b\in\omega^\omega$) $a$ $\leq_T$ $b$ implies $a$ $\leq_c$ $b$? I suspect it might be trivial, but not knowing much Recursion Theory, it's hard to see how it ...
6
votes
1answer
411 views

post correspondence problem variant

Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...
4
votes
2answers
566 views

Is the distance function from a point to the Mandelbrot set computable?

There is at least one result saying that the Mandelbrot set is undecidable, and there might be more, but I think it (or they all) use real computation rather than Turing machines. This makes some ...
5
votes
1answer
297 views

An eventually different function adding no Solovay real nor dominating function?

Definitions I believe set theorists have studied all of the following three notions in the context of forcing extensions of a model of ZFC, $M$ (hopefully the terminology is the standard one). A ...
3
votes
1answer
723 views

Homology is computable because it is stable under suspension

I've heard it said that the reason why the homology groups of a space are a computable invariant is because they are a stable invariant in the sense that they are stable under suspension. I'm ...
2
votes
5answers
513 views

Uncomputability of the identity relation on computable real numbers

Let $f_{=}$ be a function from $\mathbb{R}^{2}$ be defined as follows: (1) if $x = y$ then $f_{=}(x,y) = 1$; (2) $f_{x,y} = 0$ otherwise. I would like to have a proof for / a reference to a textbook ...
3
votes
1answer
233 views

Tuple machinery in I-Sigma_0

After thinking on Joel's answer at Computable nonstandard models for weak systems of arithemtic for a few days, I do not see how to develop enough tuple machinery in I-Sigma_0 (PA with induction ...
3
votes
1answer
476 views

Genereralized halting problem

Is it essential that it's the halting state that is considered in the Halting Problem? It seems to me that any other state of the Turing Machine would do the job, too. The problem then reads: ...
10
votes
1answer
471 views

Finite-dimensional version of the word problem for groups

The (uniform) word problem for groups can be stated in several equivalent ways: Word Problem for Groups (WP) Instance: A finite presentation of a group G and an element w of G as a product of ...
1
vote
0answers
143 views

Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed? More precisely, suppose that for any $M$ accepting coBHP={$\langle N,x,1^t\rangle|\langle ...
9
votes
2answers
1k views

Is the solution bounded Diophantine problem NP-complete?

Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, $J\leq 9$, and $M$ is a natural number. The decision problem is whether or not a given ...
9
votes
4answers
2k views

Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only. When I learnt to the topic of relativization ...
10
votes
4answers
809 views

How fast can the base-bumping function in Goodstein's theorem grow?

In the usual presentation of Goodstein's theorem, the base is bumped up by the "add 1" function. Does the theorem still hold when we replace this function by a fast-growing one (e.g. Ackermann or busy ...
1
vote
2answers
893 views

post correspondence problem

I have read a couple of proofs for the undecidability of the post correspondence problem, but neither reference gave a concrete example of two lists of words over a fixed alphabet such that the ...
5
votes
1answer
1k views

Ackermann function in the Primitive recursive arithmetic

Hello. I study primitive recursive arithmetic and have the following questions. 1) Is it possible to express in the PRA that Ackermann function is total? 2) If yes, is such expression decidable in ...
1
vote
0answers
1k views

Quantum computation implications of (P vs NP) [duplicate]

Possible Duplicate: What impact would P!=NP have on the characterization of BQP? Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that ...
11
votes
2answers
2k views

What impact would P!=NP have on the characterization of BQP?

Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
10
votes
3answers
944 views

Differentiability of computable functions

Call a computable function a total function $\mathbb{R} \to \mathbb{R}$, for which there exists a Turing machine outputting arbitrary close approximation to $f(x)$ given arbitrary close approximation ...
32
votes
8answers
4k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge: You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
7
votes
3answers
1k views

Decidable but nonrecursive sets

Until recently, I believed that recursive=decidable, subscribing to this Wikipedia quote: "In computability theory, a set is decidable, computable, or recursive if there is an algorithm that ...
5
votes
2answers
580 views

Are computable models sufficient?

What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in ...
11
votes
7answers
1k views

What happens when we print the digits of a real number?

Here are two well known facts, which put together leave me confused. First, it's well known that intuitionistic logic is the logic of constructive mathematics. From every intutionistic proof, you ...
8
votes
1answer
335 views

4-manifolds in the 4-sphere such that it, *and* its complement have unsolvable word problem

In an earlier thread I had asked whether or not one can find a smooth 4-dimensional submanifold of $S^4$ whose fundamental group has an unsolvable word problem. The answer is yes, and the reference ...
6
votes
5answers
1k views

Aren't “oracle machines” unsound concepts?

From Wikipedia (bold emphasis at the end is mine): In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as ...