Introduction to the course and algorithm complexity

This is the course introduction about algorithm complexity, including what “worst case running time” means and how it is measured.

La Life’s insight:
The key insight is here, in the following couple of minutes, after the student attempts to answer the question:

In order to determine the complexity of an algorithm, which is the basis for all kinds of results about whether stuff is computable or not, you have to make the **definitional assumption** that the algorithm is determinisitic. More precisely, you have to assume that there exist things like:
– primitive operations
– states that are inputs or outputs that the primitive operations operate on
– that these are respectively deterministic and finite

Therefore, any attempt to justify deterministic processes of stuff by algorithmic theory is circular reasoning: algorithms are assumed to be determinisitic finite state machines.

Beyond that, even if that were abstractly true, the interaction of determinisitic processes whereby a particular process modifies the primitive operation while is is computing an input, or even modifies the input while it is being processed, creates the inability to pre-determine the outcome of the computation.

An argument that well, in that case all you have to do is to break down the algorithm and the inputs into smaller finite parts, so as to reach a point where all you have is a linear succession of steps, also relies on the assumption that this is possible in a consistent, reductionist manner that is not affected by limit conditions.

One of the keys here is the notion of what "deterministic" means, more specifically what kind of operational meaning we give it: does it mean that I can predict the outcome beforehand? Does it mean that "it couldn’t have been otherwise", after the fact? There’s a big, huge in fact, difference between the two, and I think that this is largely ignored in discussions about "determinisim".

from A quoi sert la connaissance ? What is knowledge for? |


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s