1

What is the difference between an ambiguity in a proposed algorithm and an ambiguity in the representation of an algorithm?

I have done some research and found out that ambiguity in the representation of an algorithm is when the representation can be understood by a group of people and not clear to another group e.g. a layman and a programmer.

3

This is discussed in a book Computer Science: An Overview (11th Edition) by J. Glenn Brookshear, in Chapter 5 Algorithms. To start with, author formally defines algorithm as follows:

An algorithm is an ordered set of unambiguous, executable steps that defines a terminating process

Further discussion is starting at page 189. Author explains the meaning of ambiguity in what you call "proposed algorithm" as follows:

requirement imposed by the definition... is that the steps in an algorithm be unambiguous. This means that during execution of an algorithm, the information in the state of the process must be sufficient to determine uniquely and completely the actions required by each step. In other words, the execution of each step in an algorithm does not require creative skills. Rather, it requires only the ability to follow directions.

For the sake of completeness, author points out that above requirement is intentionally narrowed: "In Chapter 12 we will learn that “algorithms,” called nondeterministic algorithms, that do not conform to this restriction are an important topic of research."

Ambiguity of algorithm representation is explained as follows:

It is important to emphasize the distinction between an algorithm and its representation — a distinction that is analogous to that between a story and a book. A story is abstract, or conceptual, in nature; a book is a physical representation of a story. If a book is translated into another language or republished in a different format, it is merely the representation of the story that changes — the story itself remains the same.

In the same manner, an algorithm is abstract and distinct from its representation. A single algorithm can be represented in many ways. As an example, the algorithm for converting temperature readings from Celsius to Fahrenheit is traditionally represented as the algebraic formula

   F = (9/5)C + 32

But it could be represented by the instruction

    Multiply the temperature reading in Celsius by 9/5
    and then add 32 to the product

or even in the form of an electronic circuit. In each case the underlying algorithm is the same; only the representations differ.

The distinction between an algorithm and its representation presents a problem when we try to communicate algorithms. A common example involves the level of detail at which an algorithm must be described. Among meteorologists, the instruction “Convert the Celsius reading to its Fahrenheit equivalent” suffices, but a layperson, requiring a more detailed description, might argue that the instruction is ambiguous. The problem, however, is not with the underlying algorithm but that the algorithm is not represented in enough detail for the layperson.

Further in the chapter, author also explains how to resolve it:

the concept of primitives can be used to eliminate such ambiguity problems in an algorithm’s representation.

...A program is a representation of an algorithm. (Here we are using the term algorithm in its less formal sense in that many programs are representations of nonterminating “algorithms.”) In fact, within the computing community the term program usually refers to a formal representation of an algorithm designed for computer application.

...communication problems arise when the language used for an algorithm’s representation is not precisely defined or when information is not given in adequate detail.

Computer science approaches these problems by establishing a well-defined set of building blocks from which algorithm representations can be constructed. Such a building block is called a primitive. Assigning precise definitions to these primitives removes many problems of ambiguity, and requiring algorithms to be described in terms of these primitives establishes a uniform level of detail. A collection of primitives along with a collection of rules stating how the primitives can be combined to represent more complex ideas constitutes a programming language...

| improve this answer | |
  • 3
    thank you for expounding, i perfectly understand now, the reference too is very useful to me @gnat – mykey Jan 10 '14 at 12:07
1

There can be no ambiguity in an algorithm. By definition, an algorithm is a procedure by which a computer can achieve a task without having to make any decisions on its own. Everything it does is determined by the algorithm steps and by the input values. Therefore, any ambiguity can only be due to errors in the representation.

Note that there are non-deterministic algorithms; these choose one of a set of possible actions at one step. However, the possible actions still need to be prescribed explicitly and without ambiguity, and the source of randomness is considered an input value. The distribution of randomness is usually also considered part of the algorithm description (usually you'll want to use the best random number available, i.e. one that is equidistributed but not predictable).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.