Binary tree of finite strings ( $T \subseteq 2^{< ω}$ )

A binary tree of finite strings is a set of finite binary strings closed under taking prefixes. The empty tree is allowed; a nonempty such tree contains the empty string. Finite nodes may have no infinite extensions. Such presentations describe closed subsets of Cantor space through their infinite paths.

Table of contents
- Computable binary tree Binary tree of finite strings
  - Decidable tree for binary diagonal avoidance Computable binary tree
  - Computable pruned binary trees have computable paths Computable binary tree
- Infinite path through a binary tree Binary tree of finite strings
  - Perfect path space Infinite path through a binary tree

Computable binary tree

 0  0

A binary tree of finite strings is computable when membership of a finite binary string is decidable. An infinite computable tree need not have any computable infinite path. Removing all nodes without infinite extensions need not preserve decidability.

Decidable tree for binary diagonal avoidance

 0  0

For an effective enumeration

(φ_{e})

of unary partial computable functions, admit a length-

n

string

σ

if it disagrees with every binary value of

φ_{e} (e)

observed within

n

steps for

e < n

. The bounded halting predicate makes membership decidable, and the tests are prefix compatible. Its paths are exactly the binary diagonally noncomputable functions. The path space is nonempty and perfect because infinitely many indices of divergent programs leave arbitrarily late bits free; no path is computable. Dead ends in this decidable presentation are essential.

Computable pruned binary trees have computable paths

 0  0

For a nonempty decidable binary tree of finite strings with no terminal nodes, begin at the empty string and repeatedly choose the first immediate successor that belongs to the tree. Each finite decision terminates and some successor always exists. This produces a total computable function giving an infinite path. In particular, a nonempty decidable tree in which every node has two incompatible extensions cannot have only noncomputable paths.

Infinite path through a binary tree ( $[T] = {f \in 2^{ω} : \forall n f ↾ n \in T}$ )

 0  0

An infinite path is a binary function all of whose finite prefixes belong to the tree. Its path space

[T]

is closed in Cantor space, since failure is witnessed by one finite prefix outside

T

Perfect path space

 0  0

A nonempty path space

[T]

is perfect if it has no isolated points: for every path and every finite prefix of it there is a different path sharing that prefix. This property of the closed subset of Cantor space does not imply that its particular finite-string presentation has no dead ends. Requiring every finite node to extend to incompatible nodes is the stronger pruned-tree convention for a perfect tree.