Programatically supply workflow instead of in the DB

YES. This should work just like Views module, where export/import is offerred.

For this to really be effective, workflow states would need to be named, much like views and actions are named, because IDs are horrible for programmatic use.

Also, it's a little difficult to associate workflow with a node if the workflow table is partially in code and partially in the db, so I'd think that a module would need to write its default workflow into the database upon install. And if that's the requirement, all that's really necessary is named states.

+1 for a workflow API

Currently the way to do this is to populate the workflow tables during your module's install.

It would be useful to have a field, that declares a workflow to be created automatically, so that the user can't delete it, such as its already the case for the creation state. Further the workflow creation function workflow_create($name) should return the wid of the new workflow...

This is something of interest to me. My worry would be that after a module creates its workflow, it seems far too easy for a admin to delete it. If that workflow is vital to the functionality of the module that could be exceedingly bad. Would a system flag or something similar be something considered for addition to the workflow module or should modules doing this plan on doing fapi hacks to warn/stop users for breaking important workflows?

admins can do all sorts of bad stuff. they can delete users, delete cck types, turn site to maintainence mode, etc. there are no safeties ... yes, use fapi validator if you wan to stop this.

workflow_create returns the wid of the workflow.

Programmatic creation is important, but I'm going to postpone to 5+

Since this is being worked on here #558378: Make workflows exportable with Features (D6) and here #867186: [EXPORTING] Add machine names to workflows and workflow states I'm going to mark this one as a duplicate.