1
vote
0answers
120 views

Basis of periodic tiling of Wang tile

Given a set of Wang tile, Given 3 periodic tiling: A, B, C We define 3 vector F[A], F[B], F[C] each vector correspond to the appearing frequency of each type of tiles in the tiling. Now, we ...
6
votes
2answers
998 views

Is Turing degree actually useful in real life? [closed]

In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this? Edit: Given that we cannot explicitly and mechanically understand ...
9
votes
1answer
411 views

New research on coding in reverse mathematics?

Coding is obviously a fundamental tool in reverse mathematics, and practitioners take care to both demonstrate the correctness of their coding mechanisms and point out their limitations. Harvey ...
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) ...
-2
votes
1answer
307 views

Properties of collections (functions) that make them proper classes (uncomputable)

There are collections too big to be a set, e.g. the collection of all sets (in ZFC), and there are collections that cannot be sets for "pure" logical reasons, e.g. the collection of sets that do not ...
4
votes
6answers
901 views

Are there nonequivalent randomnesses?

There are nonequivalent geometries, nonequivalent groups finite and infinite, nonequivalent logics ( fregean and nofregean http://www.formalontology.it/suszkor.htm), even nonequivalent logicians;-) ...
13
votes
2answers
874 views

What is the most compelling reason to believe Church's thesis? [closed]

Church's thesis states that the Turing machine is a universal model of computation. What is the most compelling argument supporting this assertion?