All Questions
8 questions
45
votes
5
answers
64k
views
How large is TREE(3)?
Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation ...
- 3,630
17
votes
1
answer
960
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 ...
- 171
4
votes
4
answers
472
views
Automatically generating combinatorial conjectures
It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
- 341
3
votes
2
answers
297
views
Conjecture of a subset of Wang tile which might be decidable
From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...
- 867
3
votes
1
answer
509
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 ...
- 867
2
votes
3
answers
987
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 ...
- 867
1
vote
1
answer
631
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 ...
- 867
0
votes
1
answer
184
views
Combinatorially defined effectively closed set
Is there a combinatorially defined, nonempty effectively closed set $Q\subseteq 2^\omega$ such that all members of $Q$ are incomputable?
Combinatorially defined means that the definition of $Q$ does ...
- 909