5. Programming and composing 6. Programming styles and types
7. Algorithmic perspectives and music history
8. Musical programming and computational compositions (compugrams and algositions) 9. Conclusion: What makes algorithms and compositions different?
Mathematics and music! The most glaring possible opposites of human thought!
And yet connected, mutually sustained!
It is as if they would demonstrate the hidden consensus of all the actions of our mind, which in the revelations of genius makes us forefeel unconscious utterances
of a mysteriously active intelligence.
(Hermann v. Helmholtz, “On the Physiological Causes of Harmony in Music”, 1857)
1.1.Introduction
Algorithms provide the skeletons in computer programming and compositional plans provide the skeletons in musical productions. This is the central claim to be discussed in this chapter.
Programmers apply algorithms as they build soft structures or 'code'. This code is interpreted and executed by a computer. The product of programming is a computer program. Composers use schemes or styles to conceive sound structures encrypted as symbolic scores that are interpreted and played by performing musicians. The product of composing is a composition.
Programming creates machine contexts, while composing predominantly involves human contexts.
This may indicate, somehow circumstantially, why engineering and the arts are perceived so antagonistic in our culture. But is there a common ground ? Let us for the sake of the argument switch terms:
Composers use algorithms to build code that is executed by performers.
Programmers create structures that are played by machines.
Both domains seem to have their particular terminology with specific associations that consistently reinforce the idea of two “Snow-worlds”.1 What makes these ideas so convincing is the underlying and well-cemented conception that places the 'Arts' firmly inside the tradition of 19th c. romanticist aesthetics and on the other hand associates engineering with 'scientistic' ideologies of the 20th c.
Both views are disputable and we should be able to find logical as well as empirical space for other and less polarizing approaches.2 Let us start with the roots and nature of 'algorithm' and then clarify the concept of 'composition' in the light of this perspective.
1.2. Algorithmic sources
'Algorithm' (A) is derived from the Persian/Arabic mathematician Al-Khwarizmi and originally referred exclusively to the arithmetic rules for manipulating Arabic numbers. Nowadays, algorithm means somehow:
a definite procedure for solving problems or performing tasks. An algorithm consists of instructions how to do a task by splitting it into subtasks and sub-operations describing their order in a process.3
'Algorithm' is a 'primitive' concept. Due to its generality an exhaustive and precise definition seems impossible. Examples are easier to find though. The constructors of the Egyptian pyramids had to plan and solve their overall task of building Cheops by splitting it into subtasks. Subtasks that were temporally and spatially ordered from bottom to roof; not the other way around. Similarly, the writing of a paper, including this one, involves planning and procedures for solving each of the chapters individually, in an order that ensures overall coherence and efficiency after conclusion.
In most programming (or instructing) of computers it is necessary to be rigidly precise and
complete. Algorithms are rules and techniques (definite procedures) for writing such instructions or code. Flowcharts represent and explain algorithms. What is the connection between data (e.g.
numbers) and algorithms? Algorithms are involved with data; they use and control them. Data may be of any type, even though numbers are often favored due to their being native in 'digital'
machines. Computing today (especially in AI) uses predominantly other data types or compound data structures (as in symbolic computing). Even physical movements and perceptions for instance, are now defined and engineered algorithmically4 in robotics and sensor technologies. Algorithmic thinking shares with number systems and logics the fundamental ideas of precision and
determinedness. Algorithms and mathematical functions abide so to say to the “ideology” of
determining a unique element or step for any input or previous step (related to the notion of abstract Turing machines; see below).
But real-world problems often require decisions without sufficient knowledge at hand. And
machines by their very nature do not stand out in such open-ended environments. Neither will they adapt well to novel situations. Programmers must therefore construct closed or at least well-defined worlds to ensure that completely specified programs (algorithms) will help to avoid situations of
“doubts and hesitations” that ultimately may result in machine malfunctions.
Algorithms are vehicles used to formalize processes, actions and conditions. Algorithmic thinking goes along with civilizational processes and increases the degrees of control along with the “closing of environments”, i.e. algorithms contribute to more predictable worlds by regimenting the ruling forces and thereby reducing the informational content of situations.5 Mathematical rules that manipulate arithmetic expressions are prototype models for algorithmic formalizations. A formal criterion for well-formed algorithms is their possible implementation on (completely-specified) Turing machines6. In a Turing machine model one can intuitively relate to the 'halting problem', i.e.
whether a specific algorithm describes a terminating procedure. Non-terminating procedures, like infinite loops, prove unsuccessful as algorithms. Successful algorithms may then be tested for practical applicability on physical machines and real problems. Is a certain problem NP-complete?
Does this problem take more than polynomial time to execute?7 Engineering and technology maximize control and predictability. The question posed is what are realistic and efficient algorithms in information design (data/algorithms) and information machines (executing implementations)? To answer such questions theoretical studies of algorithms are required.
1.3 Analysis of algorithms (AA) – quantifying algorithmic power and limits
Algorithms are general approaches for finding efficient solutions to problems. The theoretical study of algorithms, the analysis of algorithms (AA), a special field of the computer sciences, consists of theoretical and empirical analyses of the properties of algorithms. AA is about algorithms i.e. meta-programming. It applies discrete mathematics and theoretical computing theory to these analyses.
Why should algorithms be analyzed at all, and not just used? Essentially for two reasons: to know which algorithms work and what resources they require. But algorithms are not programs
themselves; programs are defined at code level of specific programming languages. Algorithms are meta-programs or procedural plans that describe in general terms the behavior of many possible implementations (or programs) in any programming language. An algorithm can be written out or realized as many program code versions in different programming languages. Analogously, implemented algorithms or program code can be realized with machine code versions for various machines types and platforms. Machine code or byte code is the most concretely specified instruction type for machines; Algorithms on the other hand are the most general description of these operations.8
Algorithms are communicated through a mixture of natural and mathematical languages. AA looks for the material requirements of algorithms in terms of space (memory) and time (instruction cycles). Once a measurement language and method is established, different algorithms may be compared in order to make predictions of time and space requirements for specific algorithms based on knowledge about comparative algorithm classes.
Another aim of AA is to achieve conceptual rigidity and clarity in algorithmic design. Algorithms are classifiable as different paradigms or types. Examples of paradigms are 'divide and conquer', 'dynamic programming', 'greedy method' and 'backtracking'.
A classic algorithmic problem is the sorting of data. Sorting of unordered sets requires the finding and comparing of items, and placing and replacing items into sorted sets. All these operations require place and time in computing devices. Standard merge sort uses e.g. the “divide and conquer” strategy, that amounts to dividing the whole set into subsets that are solved recursively.
Recurrence or recursivity are essential ingredients in algorithmic complexity. Recurrence relations in AA correspond to iterative and recursive programs. The introduction of quick-sort-algorithms makes programs more efficient. Even though merge-sort is considered theoretically optimal, quick-sort does significantly reduce the running times for typical applications. This touches on premises of AA about the quality of data. What kind of practical problems can be anticipated? Allowing any kind of unsorted data set, merge-sort is the most balanced algorithm. Compared to quick-sort, it will use more resources with “standard” distributions of data, but less for somehow “odd” distributions.
Empirical and pragmatic considerations must be made in analyzing algorithms, including the use of a data or input model in addition to an algorithmic model.9 This type of considerations are the core of the different perspectives in AA. Briefly, some practitioners give priority to safe algorithms and analyze algorithms with focus at worst-case or “upper bound” performances (“computational complexity”); while others are more inclined to study applied algorithms in models that analyze average-case performance primarily (e.g. Knuth), using best-case and worst-case only as limiting conditions.
Another important concept in the AA is the generating function. Generating functions are data-describing combinatorial tools that generate enumerated combinatorial structures, also simply called symbolic method. Algorithmic objects can be formulated as ordinary, exponential or bivariate
generating functions. To understand structures in this way the symbolic method derives functional equations from generating functions that display the corresponding structural definitions.
Generating functions are tools that describe the relationships of recurrences (structural similarity) to amounts of running time and occupied space as a function of the problem size. Generating functions play a constructive role, but do also clarify complex algorithms that would otherwise be difficult to analyze. In these cases, qualified estimates of asymptotic behavior of coefficients lead to useful approximations of computational complexity (CC), employing classical mathematical functions:
In computational complexity, the O-notation is used to suppress detail of all sorts: the statements that Mergesort requires O(N log N) comparisons hides everything but the most fundamental characteristics of the algorithm, implementation and computer. In the analysis of algorithms, asymptotic expansions provide us with a controlled way to suppress irrelevant details, while preserving the most important information, especially the constant factors involved.10
CC is really more about classes of problems than classes of algorithms themselves, and brings us ultimately to the questions about tractability or non-tractability of problems in computational terms.
(see below).
Common to all methods in AA are11:
• Specification of realistic input models
• Derivation of a mathematical description of performance
• Development of concise and accurate solutions
• Comparing variants and alternative algorithms
• Adjusting values of algorithm parameters
More general models are associated with classes of combinatorial algorithms, typical of abstract and mathematical problems, as for instance in the ordering of number sets (sorting). Classes of combinatorial algorithms are studied as permutations in trees, strings, words and maps a.o. We will look at some examples:
A fundamental data-structure for algorithms are trees and forests. The more constraints we introduce the more regimented will the sorting of structures become. From the most weakly structured acyclic connected graphs, forests, unrooted trees, unordered trees, ordered trees to the most rigid or orderly binary trees. A binary tree has one top-node. An algorithm for traversing binary trees will be well-directed and economical because every node has exactly one parent-node and two child-nodes. This structure is studied a great deal because it is a naturally recursive
structure, i.e. any part of the tree is itself a subtree (of the same type). Tree data-structures and their accompanying algorithms implicitly model the behavior of recursive programs. Many properties of important algorithms are revealed through the study of trees and especially by following their tree paths. Search problems in AI belong to an early discipline that was born out of similar motivations.
Recursive tree structures lead to closed-form expressions or recursive formulations to their
generative functions. Analysis of tree algorithms express information about tree length, tree height and the specific path-lengths necessary to find “tree-solutions” to tree-conceptualized problems.
Atoms of data-structures can be of other types than numeric numbers. Characters (bytes) and sequences of characters (strings) from fixed alphabets can be atomic entities as well. Combinatorial properties of strings, words and maps are used pervasively in text-searching algorithms (string-searching), but are also useful in semantic search, e.g. on the internet. Studying sets of strings in algorithmic terms leads ultimately to the study of formal languages. There are connections between fundamental theoretical properties of formal language systems and the analytic properties of the generating functions associated with algorithms for numerical systems.
Other studies in AA are about issues of efficiency of algorithms. Generally, it is easier to measure relative differences of complexity between algorithms, e.g. variants of sorting algorithms, than to define terms like 'effective procedure' or even 'computation' in absolute terms. These basic concepts are, just like the concept of 'algorithm' itself, without formally satisfying definitions. They are primitive or intuitive concepts that have to be circumvented by analogies and examples.
Limits of algorithmic thinking and the incompleteness theorem of Kurt Gödel
Logical systems that require higher order formulations than first order logic, e.g. like the system of natural numbers12, will always contain demonstrably true and yet undecidable statements from within the expressive repertoire of Turing machines. This is Gödel's theorem in a short
approximation. Hence, the truth of those “difficult” statements (subset of all statements) cannot be proven by any formal algorithm of this language itself. This follows from the (generally accepted but not proven) Church-Turing thesis that states that Turing machines (TM) are universal machines, i.e. they are able to compute any computable problem.
This is somehow equivalent to the fact that there are functions, e.g. on the natural numbers domain (or any other data in systems that contain mathematical inductions), that cannot be computed on
TM, or in other words that there cannot be effective procedures or algorithms for computing them mechanically. Those “difficult” functions will not return answers, but will run forever on a TM, even worse so, there cannot exist any general procedure that will tell us in advance what concrete functions actually belong to this subset.
Those limitations of algorithmic thinking are called undecidability (non-provability of true statements) and non-computability (halting problem in TM) respectively.
In contrast to these absolute and theoretical limits of computability, AA quantifies the obstacles to computing, known as intractability problems. AA classifies problems as a function of the assumed time needed to solve them. Problems that exhibit polynomial growth in the time needed relative to the size of the problem are easier to solve than those problems that exhibit exponential growth in time (relative to the size of the problem). This does therefore not measure the necessary (absolute) resources for solving single algorithms, single procedures or programs; it only compares classes of problems using generalized descriptions. All the same, small problems of exponential time growth are easier to solve than big problems of polynomial time growth, so the relevance of this
classification of formal problems or algorithms grows with the size of a particular instance. In other words, undecidability and non-computability may be seen as part of a theoretical (or TM-model)
“semantics” while intractibility is better understood as theoretical “pragmatics”.
But when are problems untractable? We start with the class of P-problems that exhibit polynomial-time-growth (relative to the size of the problem). They are the easiest problems, as long as problems are not sized too big. But P-problems will be solved by the growing numbers of computing
resources in the future. The bigger sized the problem, the bigger must the resources be to solve it (O(n); O(log n)) Non-deterministic problems (NP) on the other hand can be solved in polynomial time by testing guessed solutions. In contrast to P-problems that can be solved by “brute force”, provided sufficient force, NP-problems can only be solved indirectly or heuristically. NP-problems exhibit exponential-time-growth (relative to problem size) and are therefore inherently hard problems. An assumed sub-class of NP are made up of the NP-complete problems with higher order time-growth exponentiality.13
AA is hence the theoretical study of practical algorithms and their relative efficiencies, costs and complexities. Logical and philosophical problems of computability, such as incompleteness,
undecidability, non-computability and intractability take issues of consistency and complexity into the mathematical and philosophical domain of formal systems.
1.4 Algorithmic solutions for Sudoku puzzles
Let us now construct an example algorithm for a well-known problem that applies to numbers or for that matter any other symbols: SUDOKU (S). This originally Japanese game is a puzzle that comes in several sizes (problem size!) and typically consists of a varying number of cells, ordered in rows and columns of a square or grid (figure 1). In the following example there are 6*6 cells, i.e. a grid of 36 cells (Sudoku's standard size is 9*9/81). A “S problem” starts with a subset of the total 36 numbers already filled in, called givens. Rules are as followed: only numbers from 1 to 6 are allowed and all numbers must appear once only in rows, columns as well as squares (or sub-grids)..
It is easy to see structural recurrences (see generative functions; 1.3). Besides the equal-sized sub-grids (g) of size 2*3, there are rows (r) and columns (c) of identical length. Rows and columns contain 6 cells, but in different constellations; r and c are intrinsically identical data-structures (s), rotated by 90° /270°.
A particular S (problem) always starts with certain cells filled in (pre-filled cells or givens) from the beginning. These givens function as facts. They act as premises for the filling of the remaining cells, i.e. empty cells, that must satisfy the Sudoku rules of consistency (C). Such rules state simply that any Sudoku-structure, i.e. column, row or sub-grid must contain a complete set of the possible values; in other words: no value can occur more than once, or by equivalence no value from the value domain remains unused. Valid values are in [1...6] for 6*6-grids, in [1...9] for 9*9-grids14 and so on. Facts, valid values and rules of consistency collectively constitute the conditions for filling the empty cells. What are then the subtasks and strategies in the search for valid values? And in what order should those strategies be applied to ensure efficient algorithms?
Subtasks are defined as the incremental filling of structures s (rows, columns, sub-grids). There are several obvious algorithmic strategies:
A. Scanning for determined cells first ('cross-hatching' and 'counting')
Are there structures s ={r, c, g} with a single cell left empty? If so, the remaining unused value of the value set can be filled in. We deduce its last value directly by exclusion.
If more than one cell is empty in a s, we check with intersecting s for additional constraints.
That means we look at several s at once and apply C to all. This may or may not eliminate sufficient of the remaining choices to determine further cells. If it doesn't, other strategies must be followed.
B. Eliminating candidate cells in a s
This is basically the inverse strategy of above: it eliminates possible candidate cells through looking for contingencies, i.e. narrowing down the possible locations of unused numbers to subsets of cells in a s. When subsets of cells for a specific value are also subsets of another s,
Figure 1: Sudoku grid (problem) Figure 2: Sudoko row (blue), column (yellow) and subgrid (red)
these strategies may determine or at least narrow down the options for a single cell by elimination.
C. Logical analysis (deduction from multiple constraints)
When scanning (A. or/and B.) does not supply additional fills, logical analysis must be applied, i.e. hidden relations must point to transformations and hence solutions of cells. This amounts to the collecting of statements of constraints and continual analysis for detecting of
“cell singularity”. Humans do this typically by so-called sub-script or dots notations. It implies that even non-adjacent s may contribute to the elimination of candidate cells or
“cell singularity”. Humans do this typically by so-called sub-script or dots notations. It implies that even non-adjacent s may contribute to the elimination of candidate cells or