Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T13:20:17.622Z Has data issue: false hasContentIssue false

Solution to a Problem of Spector

Published online by Cambridge University Press:  20 November 2018

A. H. Lachlan*
Affiliation:
Simon Fraser University, Burnaby, British Columbia
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In [6, p. 586] Spector asked whether given a number e there exists a unary partial function from the natural numbers into {0, 1} with coinfinite domain such that for any function ƒ into {0, 1} extending it is the case that

We answer this question affirmatively in Corollary 1 below and show that can be made partial recursive (p.r.) with recursive domain. The reader who is familiar with Spector's paper [6] will find the new trick that is required in the first paragraph of the proof of Lemma 2 below.

From one point of view, this is a theorem about trees which branch twice at every node. We shall formulate a generalization which applies to trees which branch n times at every node.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1971