Formal definition of "algorithm"?

Patrick Juola

unread,

Jul 3, 1997, 3:00:00 AM7/3/97

to

In article <MIZZARO.97...@ten.dimi.uniud.it> miz...@ten.dimi.uniud.it (Stefano Mizzaro) writes:
>But what is an algorithm? I mean, I'm aware of the classical
>definition: a procedure/receipt that is not ambiguous, made up of
>single instructions from a well defined set, and so on. But I'd like
>to have something COMPLETELY FORMAL. As "An algorithm is the set of
>all the processes belonging to an equivalence class" or whatever
>else.

The usual definition of "algorithm" is a partial recursive function
defined by some Turing machine. A Turing machine is defined
by a finite-control state machine and a tape -- the partial recursive
function defined by a given machine M is the set of (i,o) mappings
s.t. when the Turing machine M is presented with the state i on
on its initial tape, the machine eventually halts with the state o
on its tape.

-kitten

Stefano Mizzaro

unread,

Jul 3, 1997, 3:00:00 AM7/3/97

to

But what is an algorithm? I mean, I'm aware of the classical
definition: a procedure/receipt that is not ambiguous, made up of
single instructions from a well defined set, and so on. But I'd like
to have something COMPLETELY FORMAL. As "An algorithm is the set of
all the processes belonging to an equivalence class" or whatever
else.

Any ideas?
- Stefano

Hans Huttel

unread,

Jul 4, 1997, 3:00:00 AM7/4/97

to Stefano Mizzaro

Well, all the standard models of computation - Turing machines,
partial recursive functions, untyped lambda calculus etc. - constitute
(pretty successful) attempts to give a precise, completely formal
definition of the notion of algorithm. Any completely formal definition
of the notion of algorithm would constitute a model of computation.
The notion of algorithm is - by nature - an informal concept.

I could wallow in the philosophical aspects of the correspondences
between mathematical models and "reality" but I'll refrain from
that.

--
Hans Huttel, office E1-111 | ha...@cs.auc.dk
BRICS, Dept. of Computer Science | fax: (+45) 98 15 98 89
Aalborg University, Fredrik Bajersvej 7E | tel.: (+45) 96 35 88 88
9220 Aalborg \emptyset, DENMARK. | WWW:
http://www.cs.auc.dk/~hans/

Stefano Mizzaro

unread,

Jul 5, 1997, 3:00:00 AM7/5/97

to

This was my original question:

Stefano> But what is an algorithm? I mean, I'm aware of the
Stefano> classical definition: a procedure/receipt that is not
Stefano> ambiguous, made up of single instructions from a well
Stefano> defined set, and so on. But I'd like to have something
Stefano> COMPLETELY FORMAL. As "An algorithm is the set of all the
Stefano> processes belonging to an equivalence class" or whatever
Stefano> else.

These are some answers that I received (in the list and by email):

1.

Patrick> The usual definition of "algorithm" is a partial recursive
Patrick> function defined by some Turing machine. A Turing machine
Patrick> is defined by [...]

2.

Jeff> Sure. An algorithm is anything in the legal syntax of a (1)
Jeff> Turing machine definition, (2) sequence of Post productions, or
Jeff> (3) Church lambda expression.

3.

Hans> Well, all the standard models of computation - Turing machines,
Hans> partial recursive functions, untyped lambda calculus etc. -
Hans> constitute (pretty successful) attempts to give a precise,
Hans> completely formal definition of the notion of algorithm. Any
Hans> completely formal definition of the notion of algorithm would
Hans> constitute a model of computation. The notion of algorithm is
Hans> - by nature - an informal concept.

Hans> I could wallow in the philosophical aspects of the
Hans> correspondences between mathematical models and "reality" but
Hans> I'll refrain from that.

But in my opinion these (and similar ones in computability theory) are
definitions of FUNCTION or PROGRAM (or maybe "process" or
"computation"), not of ALGORITHM.

Hm?
- Stefano