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

659 views

### Groups generated by 3 involutions

Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$. Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition $\tau_{r_1(m_1),r_2(m_2)}$ be the ...
3k views

### Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?

Let ZF1 = ZF, ZFk+1 = ZF + the assumption that ZF1,...,ZFk are consistent, ZFω = ZF + the assumption that ZFk is consistent for every positive integer k, ... and similarly define ZFα ...
21k views

### What are the most attractive Turing undecidable problems in mathematics?

What are the most attractive Turing undecidable problems in mathematics? There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
1k views

### Are the two meanings of “undecidable” related?

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". I regard the ...
239 views

### Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
2k views

### How feasible is it to prove Kazhdan's property (T) by a computer?

Recently, I have proved that Kazhdan's property (T) is theoretically provable by computers (arXiv:1312.5431, explained below), but I'm quite lame with computers and have no idea what they actually ...
2k views

### Is there a computable model of ZFC?

Background Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being ...
1k 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 ...
353 views

### Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
392 views

### Can Tarski decide constructibility in elementary geometry?

Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction? The answer does ...
435 views

### Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
572 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 ...
913 views

### Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal

Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were ...
377 views

### Essential incompleteness via diophantine formulas?

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic. By a ...
276 views

### relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color. However, could we convert edge type of Wang Tile ...
6k 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 ...
5k views

### What's a magical theorem in logic?

Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less straightaway&...
1k views

### Categories of recursive functions

I have a couple of conjectures on recursive functions, that I feel must have been proved or refuted by someone else, but I don't know where to look. In short: 1. The primitive recursive functions ...
568 views

### Do decidable properties of finitely presented groups depend only on the profinitization?

This is a just-for-fun question inspired by this one. Let $P$ be a property of finitely presentable groups. Suppose that The truth of $P(G)$ only depends on the isomorphism class of $G$. Given a ...
749 views

### Are wild problems related to undecidable ones?

In representation theory, there is a well-known notion of a wild classification problem (such problems have been discussed often on this forum, for example, here). In logic, there is a notion of an ...
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)...
1k views

### Why is Kleene's notion of computability better than Banach-Mazur's?

In this post about the difference between the recursive and effective topos, Andrej Bauer said: If you are looking for a deeper explanation, then perhaps it is fair to say that the Recursive Topos ...
1k views

### Intermediate value theorem on computable reals

Wikipedia says that the intermediate value theorem “depends on (and is actually equivalent to) the completeness of the real numbers.” It then offers a simple counterexample to the ...
1k views

### Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which is guaranteed to run in polynomial time, can we computably find such a polynomial? In other words, is there a computable function $e\mapsto p_e$, ...
373 views

### Is equivalence of functions built from nested exponentiations a decidable problem?

Let $\mathcal{E}$ be the minimal set of symbolic expressions (without any predefined meaning) such that The symbol $x$ is in $\mathcal{E}$, and If expressions $P,Q\in\mathcal{E}$, then the ...
2k views

### Inverse Ackermann - primitive recursive or not?

I wanted to put this originally on math.stackexchange, since I considered it to be a straightforward question and probably a fairly known fact. After I failed to solve the problem, I browsed through ...
1k views

### Non-constructive proofs of decidability?

Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
761 views

### Antirandom reals

This is a crossposting of http://math.stackexchange.com/questions/1446602/anti-random-reals, which has not gotten any answers; after thinking about the problem, I've become more convinced that it ...
488 views

### Ackermann's function over the reals

Ackermann's function is defined over integers $x$, $y$, $A(x,y)$, with conditions for when $x{=}0$ or $y{=}0$, and otherwise uses recursive definitions involving arguments $x{-}1$ and $y{-}1$. Is ...
914 views

### Can an infinite number of mathematicians guess the number in a box with only one error?

In this question the following observation was made: Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened. Define ...
864 views

### What are the limits of non-halting?

It's easy enough to build Turing Machines that don't halt. But how complex can we make these? For example, suppose a machine has access to its state transition table and can write to it like a C ...
2k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$, decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective, respectively, injective? -- And ...
471 views

### Reverse mathematics below RCA

I'm sure this is a fairly basic question, but I can't seem to find a solid answer: My primary question is: Is there a reasonably nice subsystem of second-order arithmetic corresponding essentially to ...
282 views

### Does forcing with recursively pointed perfect trees add a Turing degree that is minimal over $V$?

A tree $T$ on $\omega$ is recursively pointed if it is recursive in each of its branches. We can consider a variant of Sacks forcing where the conditions are recursively pointed perfect trees ordered ...
906 views

### practical algorithms for np complete problems

Inspired by: Conjecture on NP-completeness of tesselation of Wang Tile up to finite size And the practicality of this topic (solving tessellation on a lattice): coloring in lattice Computational ...
735 views

### Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
1k views

### Can the twin prime problem be solved with a single use of a halting oracle?

It occurred to me that if it were possible to determine whether a given program halts, that could be used to answer the twin primes conjecture A) Write a program which takes input n and then counts ...
158 views

### Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
836 views

### Are there natural, small, and total recursive functions that are not primitive recursive?

In a sense the Ackermann function is not primitive recursive (PR) because it grows too fast. Are there total recursive, not PR, small functions? Using a diagonal argument, we may define a total ...
429 views

### Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
272 views

### Let Abit$(x,y,n)$ be the $n$th bit of Ack$(x,y)$ (the Ackermann function). Is the function “Abit” primitive recursive?

Example of "Abit": Ack$(2,3)=9=1001_2$ (base 2). Thus Abit(2,3,3)=1 (the leftmost bit of $1001$. The index of the rightmost bit is 0) Question 1: Is the function "Abit" primitive recursive (PR)? ...
378 views

### First order consequence of a combinatorial principle

(Base theory $RCA_0$)The principle says there exists a function g such that g dominates any X-recursive function for any X in the model. i.e. For any $f\le_T X$, $\exists b\in M$ such that \$g(a)>f(...
606 views

### “Rice (like) Theorem” for primitive recursive functions?

As primitive recursive (PR) functions seem to be so important (see for instance Kleene normal form Theorem) we may expect that many decision questions related to PR functions are undecidable. ...