Name
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. |
Year | DOI | Venue |
|---|---|---|
1978 | 10.1109/SFCS.1978.10 | FOCS |
Keywords | Field | DocType |
recursively enumerable,nondeterministic machine,computable nondeterministic function,noncomputable set,halting part,finite delay property,significant modification,nondeterministic model,machine model,divergence part,operating systems,polynomials,artificial intelligence,parallel processing,probability distribution,solid modeling,formal verification,computational modeling,formal languages,finite element methods,scheduling algorithm,programming,registers,automata | Discrete mathematics,Combinatorics,Generalized nondeterministic finite automaton,Formal language,Nondeterministic algorithm,Polynomial,Computer science,Automaton,Recursively enumerable language,Probability distribution,Formal verification | Conference |
Citations | PageRank | References |
15 | 20.15 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashok K. Chandra | 1 | 3116 | 1215.02 |