**12**

votes

**4**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**10**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**2**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**7**answers

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

**2**answers

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

**4**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**5**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**4**answers

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

**4**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**3**answers

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

**8**answers

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

**3**answers

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

**2**answers

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

**7**answers

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

**1**answer

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

**5**answers

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