Xiaoyan Zhang
Xiaoyan Zhang
Home
Articles
Talks
Open Problems
Contact
Light
Dark
Automatic
rK degree
n
-r.e. plus left-r.e.
Definitions Let
A
⊂
ω
.
A
is
n
-r.e. if there is a computable function
f
(
a
,
s
)
such that for all
a
∈
ω
,
f
(
a
,
0
)
=
0
,
|
{
s
:
f
(
a
,
s
)
≠
f
(
a
,
s
+
1
)
}
|
≤
n
,
lim
s
→
∞
f
(
a
,
s
)
=
χ
A
(
a
)
. Note that
1
-r.e. sets are just r.e. sets;
2
-r.
Nov 1, 2023
2 min read
Disk Game
The game Given parameters
(
l
,
c
,
q
)
. For convenience you can assume that
l
is very large,
c
=
4
and
q
=
1
/
2
. Consider the following game between a coder and a destroyer. The coder has spaces
f
(
τ
)
indexed by
τ
∈
2
≤
l
(all binary strings of length
≤
l
which are called codes).
Nov 1, 2023
1 min read
Compression of enumerations and gain
Abstract I will talk about how information in a recursive enumeration can be compressed, in the sense of relative Kolmogorov complexity (rK). We introduce a strong and a weak form of compression, and we also care about the gain of compressions.
Oct 17, 2023 12:00 AM
Hangzhou, China
Slides
Video
Compression of enumerations and gain
Abstract We study the compressibility of enumerations, and its role in the relative Kolmogorov complexity of computably enumerable sets, with respect to density. With repspect to a strong and a weak form of compression, we examine the gain: the amount of auxiliary information embedded in the compressed enumeration.
George Barmpalias
,
Xiaoyan Zhang
,
Bohua Zhan
PDF
arxiv link
Even Number Game
The game Given
k
, consider the following game of
2
players. In each round, player 1 chooses a set
R
of
k
natural numbers that he has not yet chosen earlier player 2 chooses an even number
n
∈
[
min
R
,
max
R
]
, that he has not yet chosen earlier If player 2 is unable to make a move at some round, he loses the game; otherwise he wins.
Apr 6, 2023
1 min read
Cite
×