Computable nondeterministic functions
- 1 October 1978
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 19th Annual Symposium on Foundations of Computer Science (sfcs 1978)
- p. 127-131
- https://doi.org/10.1109/sfcs.1978.10
Abstract
Functions computed on nondeterministic machines consist of two parts. The halting part which consists of outputs of halting computations, is, as expected, recursively enumerable. The divergence part, which consists of inputs for which diverging computations are possible, can however be any set in Σ11. Such highly noncomputable sets arise if one admits the "finite delay property". This implies that either we make a significant modification to our notion of "computable" as applied to nondeterministic machine models, or else that we ban the finite delay property for nondeterministic models.Keywords
This publication has 7 references indexed in Scilit:
- Computability and completeness in logics of programs (Preliminary Report)Published by Association for Computing Machinery (ACM) ,1977
- Formal verification of parallel programsCommunications of the ACM, 1976
- Parallel Program Schemata and Maximal Parallelism II: Construction of ClosuresJournal of the ACM, 1973
- A Comparison of Some Theoretical Models of Parallel ComputationIEEE Transactions on Computers, 1973
- Parallel Program Schemata and Maximal Parallelism I. Fundamental ResultsJournal of the ACM, 1973
- The correctness of nondeterministic programsArtificial Intelligence, 1970
- Parallel program schemataJournal of Computer and System Sciences, 1969