Titlebook: Mathematical Theory and Computational Practice; 5th Conference on Co Klaus Ambos-Spies,Benedikt Löwe,Wolfgang Merkle Conference proceedings

Apogee

折磨

托人看管

Program Self-reference in Constructive Scott Subdomains,em (.). Does one of these two theorems better capture the notion of program self-reference than the other? In the context of the partial computable functions over the natural numbers (), . is strictly . than ., in that . holds in any effective numbering of in which . holds, but . vice versa. It is s

incision

易怒

Optometrist

Infinite-Time Turing Machines and Borel Reducibility,achines. These results were obtained with the idea of extending the scope of the study of Borel equivalence relations, an area of descriptive set theory. I will introduce the most basic aspects of Borel equivalence relations, and show how infinite-time computation may provide insight into this area.

Baffle

Cutting Planes and the Parameter Cutwidth, polytopes. Considering . as a propositional refutation system, one can see that the cutwidth of a CNF contradiction . is always bound above by the Resolution width of .. We provide an example proving that the converse fails: there is an . which has constant cutwidth, but has Resolution width Ω(.).

GEM

Members of Random Closed Sets,m Galton-Watson trees with survival parameter .. To be such a member, a sufficient condition is to have effective Hausdorff dimension strictly greater than ., and a necessary condition is to have effective Hausdorff dimension greater than or equal to ..

DAMP

Graph States and the Necessity of Euler Decomposition,diagrammatic language to study graph states, a computationally interesting class of quantum states. We give a graphical proof of the fixpoint property of graph states. We then introduce a new equation, for the Euler decomposition of the Hadamard gate, and demonstrate that Van den Nest’s theorem—loca

crease