New computing paradigms suggested by DNA computing: computing by carving

Inspired by the experiments in the emerging area of DNA computing, a somewh at unusual type of computation strategy was recently proposed by one of us: to generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. This has been called a computation by carving. This idea leads both to a speculatio n with possible important consequences-computing non-recursively enumerable languages-and to interesting theoretical computer science (formal language ) questions. (C) 1999 Elsevier Science Ireland Ltd. All rights reserved.