Discrete Mathematics for Computer Science

Uncomputability 317

ited time and memory resources, one can implement arithmetic procedures on arbitrarily

large integers and do string manipulation functions on arbitrarily long (but finite) character

strings. To keep things simple, however, we shall merely assume that our language allows

arbitrarily long character strings. Other than that, we use our algorithm notation; the same

constructions could be carried out in almost any common modem programming language.

The idea of a function subprogram, although we have used it informally before, needs

to be made explicit for this discussion. In particular, we need to formalize the idea of a

return value-a value returned by the function and then used by the rest of the program. A

function subprogram is a string of characters of the formfunctionName(paral, para 2 .....

paraN) where N can be any integer. The terms para 1, para 2 ... , paraN are valid variable

or data types in the program that are made available to the code of the function subprogram.

We call the statement functionName(para , para 2 ... ,paraN) a function call. The result

of executing the function call is the "return" of a single value to the program that is then

substituted for the function call. The returned value may be a numeric value, a boolean

value, or a character string. At some point of the program, it should be made clear what kind

of value is being returned by a function call. How that is done, however, is not necessary

for us to consider during this discussion.

At some level, humans ordinarily interact with computers through strings of charac-

ters. We shall simplify the context by assuming that each program takes just one character

string as input. That is, all its input is concatenated together into one (usually very long)

string. Similarly, assume that the program either has no output (if it never halts) or outputs

a single (perhaps very long) character string. Furthermore, consider a program itself to be

a single, long character string-again simply a concatenation of all the lines of code of the

algorithm.

Definition 1. (Rather arbitrary, and adopted for convenience.) An algorithm A is a pro-

cedure written in some programming language that is passed a single character string In,

which is referred to as the algorithm's input, and returns a character string Out, which is

referred to as the algorithm's return value (and which we may also think of as an output).

The string Out is also called A (In). On some (or all) inputs, an algorithm may never halt;

thus, it may return nothing. If it halts but has no apparent output, as when the algorithm

stops because of a run-time error, we shall think of it as returning the empty string.

Example 1. Foo(wordl)

if word 1 < "M

return word 1

else

return "Wrong starting letter"

is an algorithm that takes any string as input and determines whether the word begins with

one of the letters "A", "B", or "C". (For simplicity, we assume the only other possibilities

are D-Z.) If the word satisfies the condition, the word itself is returned. If the word does

not satisfy the condition, the string "Wrong starting letter" is returned.

We stipulate that the machine on which algorithm A is run can store arbitrarily long
strings. Presumably, then, it can also store arbitrarily large integers, arbitrarily large ar-
rays, and arbitrarily long lists, but allowing just arbitrarily long strings suffices for this
discussion.