Implementability Among Predicates
- Creators
- Cook, Matthew
- Bruck, Jehoshua
Abstract
Much work has been done to understand when given predicates (relations) on discrete variables can be conjoined to implement other predicates. Indeed, the lattice of "co-clones" (sets of predicates closed under conjunction, variable renaming, and existential quantification of variables) has been investigated steadily from the 1960's to the present. Here, we investigate a more general model, where duplicatability of values is not taken for granted. This model is motivated in part by large scale neural models, where duplicating a value is similar in cost to computing a function, and by quantum mechanics, where values cannot be duplicated. Implementations in this case are naturally given by a graph fragment in which vertices are predicates, internal edges are existentially quantified variables, and "dangling edges" (edges emanating from a vertex but not yet connected to another vertex) are the free variables of the implemented predicate. We examine questions of implementability among predicates in this scenario, and we present the solution to all implementability problems for single predicates on up to three boolean values. However, we find that a variety of proof methods are required, and the question of implementability indeed becomes undecidable for larger predicates, although this is tricky to prove. We find that most predicates cannot implement the 3-way equality predicate, which reaffirms the view that duplicatability of values should not be assumed a priori.
Additional Information
We would like to thank Erik Winfree for helpful discussions. This research was supported in part by the "Alpha Project" that is funded by a grant from the National Human Genome Research Institute (Grant No. P50 HG02370). http://www.paradise.caltech.edu/papers/etr067.pdfFiles
Name | Size | Download all |
---|---|---|
md5:ec097dab3fef667480af18566adf2a47
|
287.4 kB | Preview Download |
Additional details
- Eprint ID
- 26094
- Resolver ID
- CaltechPARADISE:2005.ETR067
- Created
-
2005-03-22Created from EPrint's datestamp field
- Updated
-
2019-11-22Created from EPrint's last_modified field
- Caltech groups
- Parallel and Distributed Systems Group