2
$\begingroup$

A chain-complete partial order (equivalently, a pointed dcpo) is a set $D$ with a partial order $\leq$ such that all chains of $D$ have a supremum. The least upper bound ($\bigsqcup$) of the empty chain is the least element $\bot$ of the CCPO.

A function $f\colon M \to N$ is monotone if for all $a, b \in M$, the following holds: $$a \leq b \implies f(a) \leq f(b)$$

A function $f\colon M \to N$ between two CCPOs is Scott-continuous if it is monotone and for every chain $C$ of $M$, we have

$$f(\bigsqcup_{c \in C} c) = \bigsqcup_{m \in C} f(c)\,.$$

Scott-continuous functions play an important part in defining denotational semantics of programs, and as is well-known in computing science, every Turing-computable function is Scott-continuous$^0$. Is the converse true? Is every Scott-continuous function computable?


  1. See this question, from which I took and edited some definitions.
$\endgroup$

1 Answer 1

2
$\begingroup$

$\newcommand{\TM}{T\!M}$

Let $\TM$ be the set of Turing machines and $2 = \{0,1\}$.

The powerset of any set with $\leq$ equal to $\subseteq$ is a CCPO, its least upper bounds being the unions of the chains.

Take the function $f\colon P(\TM) \to P(\TM \times 2)$ that maps a set of Turing machines $S$ to $$\{ (t, h) \mid t \in S \text{ and $h$ equals whether $t$ halts on empty input } \}$$

The function $f$ is Scott-continuous $-$ it is defined pointwise, so it's monotonous and $$f(\bigcup_{c \in C} c) = \bigcup_{c \in C} f(c)\,,$$ and therefore $$f(\bigsqcup_{c \in C} c) = \bigsqcup_{c \in C} f(c)\,.$$

It is also obviously not computable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.