All Questions
11 questions
12
votes
4
answers
4k
views
reversible Turing machines
Hello,
Let T be a Turing machine such that
1) it operates on the alphabet {0,1},
2) its set of states is A
3) the language it accepts is $L$ .
Does there exists a Turing machine S which also ...
- 236k
29
votes
2
answers
1k
views
Determining if a rational function has a subtraction-free expression
This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
- 91.8k
5
votes
0
answers
301
views
The expressiveness of functions computable on trees
Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
CommunityBot
- 1
26
votes
6
answers
9k
views
The problem of finding the first digit in Graham's number
Motivation
In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
1
vote
1
answer
243
views
A possible minimal aperiodic set of corner Wang Tile
From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...
- 4,713
5
votes
1
answer
213
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 ...
CommunityBot
- 1
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 ...
- 13.4k
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 ...
CommunityBot
- 1
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 ...
- 236k
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1