<p>The domain-theoretic considerations of the kind you are asking about can be carried out using <a href="https://ncatlab.org/nlab/show/synthetic+domain+theory" rel="noreferrer">synthetic domain theory</a>. Related to it is <a href="https://ncatlab.org/nlab/show/synthetic+topology" rel="noreferrer">syntehtic topology</a>, and in fact the two share many common ideas.</p>
<p>The starting point of both synthetic approaches is the observation that the <a href="https://ncatlab.org/nlab/show/Sierpinski+space" rel="noreferrer">Sierpinski space</a> <span class="math-container">$\Sigma$</span> classifies open sets, i.e., given a space or a domain <span class="math-container">$X$</span>, the space <span class="math-container">$\mathcal{C}(X, \Sigma)$</span> of continuous maps is in bijective correspondence with the open subsets of <span class="math-container">$X$</span>. The general approach then is as follows:</p>
<ol>
<li><p>Pick a suitable category <span class="math-container">$\mathcal{E}$</span>, to serve as an ambient in which we carry out the &quot;synthetic&quot; version of topology or domain theory.</p>
</li>
<li><p>Construct an object <span class="math-container">$\mathbb{S}$</span> in <span class="math-container">$\mathcal{E}$</span>, together with a suitable additional structure, which plays the role of the Sierpinski space. The suitable additional structure is that of a <a href="https://ncatlab.org/nlab/show/dominance" rel="noreferrer">dominance</a>.</p>
</li>
<li><p>Use the exponential object <span class="math-container">$\mathbb{S}^X$</span> as the &quot;topology&quot; of <span class="math-container">$X$</span>.</p>
</li>
</ol>
<p>Examples of such setups can be found in the literature on synthetic domain theory. Another source is Davorin Lešnik's PhD (write him an email). The usual topology can be obtained by taking <span class="math-container">$\mathcal{E}$</span> to be a suitable topos of sheaves on topological spaces.</p>
<p>A computable version of domain theory and topology can be obtained by taking <span class="math-container">$\mathcal{E}$</span> to be the <a href="https://ncatlab.org/nlab/show/effective+topos" rel="noreferrer">effective topos</a> as follows. Let <span class="math-container">$W$</span> be a standard enumeration of the c.e. sets and <span class="math-container">$K$</span> the <em>halting set</em></p>
<p><span class="math-container">$$K = \{n \in \mathbb{N} \mid n \in W_n\}.$$</span></p>
<p>That is, <span class="math-container">$n \in K$</span> when the <span class="math-container">$n$</span>-th Turing machine terminates on input <span class="math-container">$n$</span>.</p>
<p>Define <span class="math-container">$\mathbb{S}$</span> to be the <a href="http://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf" rel="noreferrer">assembly</a> <span class="math-container">$\mathbb{S} = (\{\bot, \top\}, {E_\mathbb{S}})$</span> whose existence predicate is
<span class="math-container">$$E_\mathbb{S}(\top)= K
\qquad\qquad
E_\mathbb{S}(\bot)= \mathbb{N} \setminus K.$$</span>
In the effective topos <span class="math-container">$\mathbb{S}^\mathbb{N}$</span> is the assembly of c.e. sets, and in general <span class="math-container">$\mathbb{S}$</span> behaves like a computable Sierpinski space.</p>
<p>Now we are ready to propose a suitable setup for infinite-time Turing machines (IITM). Let <span class="math-container">$K_\infty$</span> be the halting set for IITMS's:</p>
<p><span class="math-container">$$K_\infty = \{n \in \mathbb{N} \mid \text{the $n$-th IITM halts on input $n$}\}.$$</span></p>
<p>If I were to investigate domain theory for IITM's, I would consider the realizability topos built over the partial combinatory algebra of IITM's (see <a href="http://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf" rel="noreferrer">these notes</a>). The dominance is <span class="math-container">$\mathbb{S}_\infty = (\{\bot, \top\}, {E_{\mathbb{S}_\infty}})$</span> where
<span class="math-container">$$E_{\mathbb{S}_\infty}(\top)= K_\infty
\qquad\qquad
E_{\mathbb{S}_\infty}(\bot)= \mathbb{N} \setminus K_\infty.$$</span>
The resulting notion of synthetic topology is &quot;intrinsic&quot; to IITMs. For example <span class="math-container">$\mathbb{S}_\infty^\mathbb{N}$</span> will be those subsets of <span class="math-container">$\mathbb{N}$</span> which are the halting sets of an IITM, I think. I am not sure eactly, because with IITMs strange things happen. Is it the case that a set is the halting set of an IITM if and only if it is enumerated by an IITM?</p>
<p>There are many other possible variations, both on how we construct a topos from IITMs, and what we take as <span class="math-container">$\mathbb{S}$</span>. I am not aware of any serious study of what works and what does not. Take everything I said here as just unbaked ideas that might show some promising directions.</p>

CC BY-SA 4.0
2022-06-06T12:53:20.760Z
2022-06-06T12:53:20.760Z
Andrej Bauer
<p><span class="math-container">$\newcommand{\tb}{2_{\!\bot}}\newcommand{\tbO}{\tb^{\,\omega}}$</span>Let <span class="math-container">$2 = \{0,1\}$</span> and <span class="math-container">$\tb = \{0,\bot,1\}$</span>.</p>
<p>Scott continuity is important for defining models of lambda calculus,
a formalism for defining Turing-computable functions. That is because every
Turing/lambda-computable function is Scott-continuous, and there are domains such that
<span class="math-container">$$D \cong [D \to D]\,,$$</span>
where <span class="math-container">$[D \to D]$</span> is the set of Scott-continuous functions on <span class="math-container">$D$</span>.</p>
<p>Infinite time Turing machines (ITTMs) are more expressive than Turing machines, and are capable of computing functions that are not Scott-continuous. Take the function
<span class="math-container">$z\colon 2^\omega \to 2$</span> that returns 0 iff its argument is a tape of zeros. (An ITTM may cycle moving left, return 1 if it finds 1 on the tape, or return 0 if it finds itself in the limit state. However, <span class="math-container">$z$</span> is not Scott-continuous, see below.)</p>
<p><strong>Question</strong>: Is there some other continuity <span class="math-container">$Y$</span> that would similarly be to ITTM-computable functions what Scott continuity is to Turing-computable functions?</p>
<p>It would have to be the case that all ITTM-computable functions are <span class="math-container">$Y$</span>-continuous. Presumably, there would also be domains isomorphic to their <span class="math-container">$Y$</span>-continuous function spaces, containing all ITTM-computable functions. (I don't know what other, if any, requirements I should have.)</p>
<hr />
<p>Definitions:</p>
<p>Let <span class="math-container">$&lt;$</span> be a partial order on <span class="math-container">$\tb$</span> such that only <span class="math-container">$\bot &lt; 0$</span> and <span class="math-container">$\bot &lt; 1$</span> hold. Let <span class="math-container">$\tbO$</span>
be ordered pointwise.</p>
<p>A pointed directed-complete partial order (CPO) is a partially ordered set with a least element, such that every directed set has a supremum. <span class="math-container">$\tbO$</span> and <span class="math-container">$\tb$</span> are CPOs.</p>
<p>Let <span class="math-container">$D$</span> and <span class="math-container">$E$</span> be CPOs. A function <span class="math-container">$f\colon D \to E$</span> is Scott continuous iff for every directed subset <span class="math-container">$P$</span> of <span class="math-container">$D$</span>, its image has a supremum <span class="math-container">$\sqcup f(P)$</span> and it equals <span class="math-container">$f(\sqcup P)$</span>.</p>
<p>I believe it is reasonable to extend the definition of Scott continuity to functions <span class="math-container">$g\colon 2^\omega \to 2$</span> as follows, but if I'm wrong here, please correct me:
<span class="math-container">$g$</span> is continuous iff the following function is:
<span class="math-container">\begin{align}
  g'\colon \tbO &amp;\to \tb \\
  x &amp;\mapsto \sqcap g(\{ y \in 2^\omega \mid x \leq y \})
\end{align}</span></p>
<p>(I believe this corresponds with how continuity of <span class="math-container">$g$</span> is defined in
<a href="https://cs.stackexchange.com/a/81018/71063">this answer</a> using the product topology
on <span class="math-container">$2^\omega$</span>, and has the intuitive explanation that we are treating elements of <span class="math-container">$\tb^\omega$</span> as sequences of finite pieces of information about some element of <span class="math-container">$2^\omega$</span>, each piece telling us the value of the corresponding digit (if it's 0 or 1) or that the digit is unknown (if it's <span class="math-container">$\bot$</span>). If this is unreasonable (or incorrect), then unfortunately I don't know how one might extend the definition of Scott continuity to functions from <span class="math-container">$2^\omega$</span> to <span class="math-container">$2$</span>; hopefully my question can still be salvaged.)</p>
<p>With this definition, we might show why <span class="math-container">$z$</span> from above is not Scott-continuous: for every <span class="math-container">$n \in \mathbb{N}$</span>, let <span class="math-container">$Z_n = 0^n \cdot \bot^\omega$</span>, where <span class="math-container">$\cdot$</span> is concatenation. For every <span class="math-container">$n$</span>, <span class="math-container">$z'(Z_n) = \bot$</span>, so <span class="math-container">$\sqcup_n z'(Z_n) = \bot$</span>, however <span class="math-container">$z'(\sqcup_n Z_n) = z'(0^\omega) = 0$</span>.</p>

CC BY-SA 4.0
2022-06-05T06:54:52.480Z
Are you familiar with synthetic domain theory? An appropriate notion of continuity for IITM's can be devised by taking a suitable dominance in the realizaiblity topos over IITM model.
Andrej Bauer
CC BY-SA 4.0
2022-06-05T09:53:07.083Z
No, but since I'll very likely need such a (or a similar) notion of continuity, I'll be glad to learn, even if it takes time.
Jozef Mikušinec
CC BY-SA 4.0
2022-06-06T11:52:24.930Z
I only have general references that will require some background reading, not anything specific to IITMs.
Andrej Bauer
CC BY-SA 4.0
2022-06-26T22:07:17.903Z
might be related: There has been a lot of work in the area of Computable Analysis. A good place is the book Computable Analysis by Klaus Weihrauch. iirc, chapter 7 has is a survey of other approaches.
Kaveh
CC BY-SA 4.0
2022-06-26T22:21:51.173Z
by the way, the more typical way to approximate infinitive sequences is too use finite initial prefixes (nodes in the $2^\omega$ viewed as a tree), it simplifies things. https://en.wikipedia.org/wiki/Computable_analysis
Kaveh
<computability><domain-theory>
An analogue of Scott continuity for infinite-time-Turing-computable functions
Jozef Mikušinec
# An analogue of Scott continuity for infinite-time-Turing-computable functions

(Asked by: username_0 on 2022-06-04)

$\newcommand{\tb}{2\_{\!\bot}}\newcommand{\tbO}{\tb^{\,\omega}}$Let $2 = \{0,1\}$ and $\tb = \{0,\bot,1\}$.

Scott continuity is important for defining models of lambda calculus,
a formalism for defining Turing-computable functions. That is because every
Turing/lambda-computable function is Scott-continuous, and there are domains such that
$$D \cong [D \to D]\,,$$
where $[D \to D]$ is the set of Scott-continuous functions on $D$.

Infinite time Turing machines (ITTMs) are more expressive than Turing machines, and are capable of computing functions that are not Scott-continuous. Take the function
$z\colon 2^\omega \to 2$ that returns 0 iff its argument is a tape of zeros. (An ITTM may cycle moving left, return 1 if it finds 1 on the tape, or return 0 if it finds itself in the limit state. However, $z$ is not Scott-continuous, see below.)

**Question**: Is there some other continuity $Y$ that would similarly be to ITTM-computable functions what Scott continuity is to Turing-computable functions?

It would have to be the case that all ITTM-computable functions are $Y$-continuous. Presumably, there would also be domains isomorphic to their $Y$-continuous function spaces, containing all ITTM-computable functions. (I don't know what other, if any, requirements I should have.)

---

Definitions:

Let $<$ be a partial order on $\tb$ such that only $\bot < 0$ and $\bot < 1$ hold. Let $\tbO$
be ordered pointwise.

A pointed directed-complete partial order (CPO) is a partially ordered set with a least element, such that every directed set has a supremum. $\tbO$ and $\tb$ are CPOs.

Let $D$ and $E$ be CPOs. A function $f\colon D \to E$ is Scott continuous iff for every directed subset $P$ of $D$, its image has a supremum $\sqcup f(P)$ and it equals $f(\sqcup P)$.

I believe it is reasonable to extend the definition of Scott continuity to functions $g\colon 2^\omega \to 2$ as follows, but if I'm wrong here, please correct me:
$g$ is continuous iff the following function is:
\begin{align}
g'\colon \tbO &\to \tb \\
x &\mapsto \sqcap g(\{ y \in 2^\omega \mid x \leq y \})
\end{align}

(I believe this corresponds with how continuity of $g$ is defined in
[this answer](https://cs.stackexchange.com/a/81018/71063) using the product topology
on $2^\omega$, and has the intuitive explanation that we are treating elements of $\tb^\omega$ as sequences of finite pieces of information about some element of $2^\omega$, each piece telling us the value of the corresponding digit (if it's 0 or 1) or that the digit is unknown (if it's $\bot$). If this is unreasonable (or incorrect), then unfortunately I don't know how one might extend the definition of Scott continuity to functions from $2^\omega$ to $2$; hopefully my question can still be salvaged.)

With this definition, we might show why $z$ from above is not Scott-continuous: for every $n \in \mathbb{N}$, let $Z\_n = 0^n \cdot \bot^\omega$, where $\cdot$ is concatenation. For every $n$, $z'(Z\_n) = \bot$, so $\sqcup\_n z'(Z\_n) = \bot$, however $z'(\sqcup\_n Z\_n) = z'(0^\omega) = 0$.

**Tags:** computability, domain-theory

> **Comments:**
> **username_1**: Are you familiar with synthetic domain theory? An appropriate notion of continuity for IITM's can be devised by taking a suitable dominance in the realizaiblity topos over IITM model.  
> **username_0**: No, but since I'll very likely need such a (or a similar) notion of continuity, I'll be glad to learn, even if it takes time.  
> **username_1**: I only have general references that will require some background reading, not anything specific to IITMs.  
> **username_2**: might be related: There has been a lot of work in the area of Computable Analysis. A good place is the book Computable Analysis by Klaus Weihrauch. iirc, chapter 7 has is a survey of other approaches.  
> **username_2**: by the way, the more typical way to approximate infinitive sequences is too use finite initial prefixes (nodes in the $2^\omega$ viewed as a tree), it simplifies things. https://en.wikipedia.org/wiki/Computable_analysis  

---

## 1 answers

### Answer by username_1 on 2022-06-06. Score: 7

The domain-theoretic considerations of the kind you are asking about can be carried out using [synthetic domain theory](https://ncatlab.org/nlab/show/synthetic+domain+theory). Related to it is [syntehtic topology](https://ncatlab.org/nlab/show/synthetic+topology), and in fact the two share many common ideas.

The starting point of both synthetic approaches is the observation that the [Sierpinski space](https://ncatlab.org/nlab/show/Sierpinski+space) $\Sigma$ classifies open sets, i.e., given a space or a domain $X$, the space $\mathcal{C}(X, \Sigma)$ of continuous maps is in bijective correspondence with the open subsets of $X$. The general approach then is as follows:

1. Pick a suitable category $\mathcal{E}$, to serve as an ambient in which we carry out the "synthetic" version of topology or domain theory.
2. Construct an object $\mathbb{S}$ in $\mathcal{E}$, together with a suitable additional structure, which plays the role of the Sierpinski space. The suitable additional structure is that of a [dominance](https://ncatlab.org/nlab/show/dominance).
3. Use the exponential object $\mathbb{S}^X$ as the "topology" of $X$.

Examples of such setups can be found in the literature on synthetic domain theory. Another source is Davorin Lešnik's PhD (write him an email). The usual topology can be obtained by taking $\mathcal{E}$ to be a suitable topos of sheaves on topological spaces.

A computable version of domain theory and topology can be obtained by taking $\mathcal{E}$ to be the [effective topos](https://ncatlab.org/nlab/show/effective+topos) as follows. Let $W$ be a standard enumeration of the c.e. sets and $K$ the *halting set*

$$K = \{n \in \mathbb{N} \mid n \in W\_n\}.$$

That is, $n \in K$ when the $n$-th Turing machine terminates on input $n$.

Define $\mathbb{S}$ to be the [assembly](http://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf) $\mathbb{S} = (\{\bot, \top\}, {E\_\mathbb{S}})$ whose existence predicate is
$$E\_\mathbb{S}(\top)= K
\qquad\qquad
E\_\mathbb{S}(\bot)= \mathbb{N} \setminus K.$$
In the effective topos $\mathbb{S}^\mathbb{N}$ is the assembly of c.e. sets, and in general $\mathbb{S}$ behaves like a computable Sierpinski space.

Now we are ready to propose a suitable setup for infinite-time Turing machines (IITM). Let $K\_\infty$ be the halting set for IITMS's:

$$K\_\infty = \{n \in \mathbb{N} \mid \text{the $n$-th IITM halts on input $n$}\}.$$

If I were to investigate domain theory for IITM's, I would consider the realizability topos built over the partial combinatory algebra of IITM's (see [these notes](http://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf)). The dominance is $\mathbb{S}\_\infty = (\{\bot, \top\}, {E\_{\mathbb{S}\_\infty}})$ where
$$E\_{\mathbb{S}\_\infty}(\top)= K\_\infty
\qquad\qquad
E\_{\mathbb{S}\_\infty}(\bot)= \mathbb{N} \setminus K\_\infty.$$
The resulting notion of synthetic topology is "intrinsic" to IITMs. For example $\mathbb{S}\_\infty^\mathbb{N}$ will be those subsets of $\mathbb{N}$ which are the halting sets of an IITM, I think. I am not sure eactly, because with IITMs strange things happen. Is it the case that a set is the halting set of an IITM if and only if it is enumerated by an IITM?

There are many other possible variations, both on how we construct a topos from IITMs, and what we take as $\mathbb{S}$. I am not aware of any serious study of what works and what does not. Take everything I said here as just unbaked ideas that might show some promising directions.


---

