lets pretend “number of bits needed to describe X” means “log2 the length of the shortest theory that proves the existence of X.”
Whether a theory proves the existence of X may be an undecideable question.
How many bits it takes to describe X is an undecidable question when defined in other ways, too.
The definition “length of the shortest program which minimizes (program length + runtime)” isn’t undecideable, although you could argue that that’s not what we normally mean by number of bits.
Adding program length and runtime feels to me like a type error.
Current theme: default
Less Wrong (text)
Less Wrong (link)
Arrow keys: Next/previous image
Escape or click: Hide zoomed image
Space bar: Reset image size & position
Scroll to zoom in/out
(When zoomed in, drag to pan; double-click to close)
Keys shown in yellow (e.g., ]) are accesskeys, and require a browser-specific modifier key (or keys).
]
Keys shown in grey (e.g., ?) do not require any modifier keys.
?
Esc
h
f
a
m
v
c
r
q
t
u
o
,
.
/
s
n
e
;
Enter
[
\
k
i
l
=
-
0
′
1
2
3
4
5
6
7
8
9
→
↓
←
↑
Space
x
z
`
g
Whether a theory proves the existence of X may be an undecideable question.
How many bits it takes to describe X is an undecidable question when defined in other ways, too.
The definition “length of the shortest program which minimizes (program length + runtime)” isn’t undecideable, although you could argue that that’s not what we normally mean by number of bits.
Adding program length and runtime feels to me like a type error.