Abstract:
Synthetic pattern generation procedures have various applications,
and a number of approaches (fractals, L-systems, etc.) have been
devised. A fundamental underlying question is: will new pattern
generation algorithms continue to be invented, or is there some
“universal” algorithm that can generate all (and only) the perceptually
distinguishable images, or even all members of a restricted
class of patterns such as logos or letterforms? In fact there are many
complete algorithms that can generate all possible images, but most
images are random and not perceptually distinguishable. Counting
arguments show that the percentage of distinguishable images
that will be generated by such complete algorithms is vanishingly
small. In this paper we observe that perceptually distinguishable
images are compressible. Using this observation it is evident that
algorithmic complexity provides an appropriate framework for discussing
the question of a universal image generator. We propose
a natural Thesis for describing perceptually distinguishable images
and argue its validity. Based on it, we show that there is no program
that generates all (and only) these images. Although this is an
abstract result, it may have import for several areas in graphics that
deal with compressible signals. In essence, new representations and
pattern generation algorithms will continue to be developed; there
is no feasible “super algorithm” that is capable of all things.