0
votes
0answers
64 views

Linkage between homotopy equivalence and identification of algorithms

I vaguely recall that someone says there is linkage between homotopy equivalence and identification of algorithms which may be isomorphic or morphism or something like that,the algorithm may be ...
2
votes
2answers
127 views

How to define the input of computable function or Turing machine over real numbers

Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
7
votes
4answers
509 views

(reference request) Chaitin's constant is incompressible

I've been looking for a full, detailed proof that Chaitin's constant is incompressible, i.e. there is a universal constant $c$ such that every program writing first $n$ digits of $\Omega$ has length ...
3
votes
3answers
735 views

An established proof in Wang Tile which I doubt

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf I could not ...
7
votes
1answer
350 views

Demuth's theorem in set theory

I am quite sure the following fact must have been known for set theorists, though I could not find it anywhere. If $r$ is random over $L$ and $x\in L[r]\setminus L$, then there must be some real ...
6
votes
2answers
221 views

Only admissibles start gaps in clockable ordinals

This is a question about ITTM model introduced by Hamkins et al. In this paper it is proven that no admissible ordinal is clockable, so it either starts or lies within a gap in clockable ordinals. I ...
2
votes
0answers
102 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
5
votes
1answer
116 views

Attribution of an equivalence of the existence of omega-models of RCA0

There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of ...
2
votes
0answers
90 views

Comparing two non-deterministic Turing equivalents as basis for Logic, request for references

I am designing a logic, that is simpler than FOL + PA. And I like to know if there already exists something in this direction. First of all a non-deterministic Turing equivalent is defined by ...
3
votes
1answer
198 views

Reverse mathematics, Ramsey theorem and mass problem

If we look at reverse mathematics statements as mass problems, considering the class of solutions of an instance, it is known that Weak K├Ânig's lemma has a maximal instance in the sense that there is ...
8
votes
2answers
346 views

Where should I learn about Kolmogorov complexity of overlapping substrings?

I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, ...
9
votes
2answers
385 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 ...
20
votes
0answers
798 views

Godel on recursion-theoretic hierarchies

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes: "Another mathematical eternal return: Toward the end of his ...
18
votes
1answer
763 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 ...
5
votes
1answer
209 views

Notion of independence of Turing degrees

I've been thinking for a while about different ways two Turing degrees might be "independent" of each other (from the point of view of computability theory). The simplest such notion would be to say ...
6
votes
1answer
268 views

Status of the Isomorphism problem for automatic groups?

I only ask because I don't know how to look for the answer.
3
votes
0answers
143 views

Alternate proof of van de Wiele's theorem in E-recursion

Hello, all I'm currently trying to understand $E$-recursion theory, which is a generalization of classical recursion theory to arbitrary sets. One of the difficulties I'm having with understanding ...
4
votes
1answer
210 views

Reference for a “recursive” fragment of infinitary logic?

Does anyone know of any texts or papers out there concerning properties of the fragment of $ \mathcal{L}_{\omega_1, \omega} $ in which the only admissable infinite conjunctions are those which are ...
4
votes
1answer
443 views

Infinite monkeys computing … triangle area?

I wonder if it is possible to specialize the question: (a) What is the probability that a random Turing Machine program will halt?, to: (b) What is the probability that a random Turing Machine ...
12
votes
1answer
615 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 ...
5
votes
1answer
378 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 ...
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 ...
12
votes
3answers
904 views

Has there ever been a weaker Church-like thesis?

Background. The Church-Turing thesis, in one of its many equivalent formulations, states that the intuitively computable arithmetical functions are exactly those computed by Turing machines. ...
7
votes
3answers
872 views

Is there a “primitive-recursively enumerable” set whose complement is not such?

Call a subset of $\mathbb{N}$ primitive-recursively enumerable (p-r.e.) if it is empty or an image of a primitive recursive function. I feel like a lot must be known about the poset of such sets ...
11
votes
3answers
740 views

Alive dynamical system

Intuitively, one can say that a dynamical system is alive if one can build a universal Turing machine inside. So, Conway's Game of Life is alive and shift space should be dead. I fail to make this ...