Computing with shapes

Visual languages represent a response to the communicational challenges posed by end-user computing, but lack established computability frameworks for evaluating their computational power. In this paper, we introduce a computability model-called shape completion system-for the restricted, but important, case in which the visual representation of the concepts to be communicated is built as a puzzle. Shape completion systems are based on adjoining polyominoes, shapes from a basic set. A description in the form of a string on some alphabet can be associated with each basic shape. A computation in a shape completion system is correct when: (1) it starts by using a specified polyomino; (2) it ends when a rectangle is obtained (without holes); (3) at any step the current picture is connected; and (4) a sequencing mapping is given, so that at every step (except the first one) we use a polyomino depending on the previously used polyomino, as specified by this mapping (such a condition is essential for interactive visual languages, as formalized in [1, 2]). We also establish how symbols associated with the polyominoes are concatenated to form strings in a string language associated with the computation. Surprisingly enough, in these circumstances we can characterize the recursively enurnerable languages (hence the power of Turing machines). If we preserve only conditions (1), (2) and (3) above, then we cannot generate all linear languages but we can generate all regular languages and strictly more: also some one-letter non-regular languages can be obtained. In particular, we can obtain as correct computations squares only, which is often a difficult task in picture languages (see, e.g. [3]). (C) 2001 Academic Press.