`(0.999... = 1)`

,
which we'll see in detail in a moment.
$\begin{aligned}
\hat Q(q) = \top \iff q \in Q \\
\hat Q(q) = \bot \iff q \notin Q \\
\end{aligned}$

Where $\top$ signifies stopping at a state and returning `TRUE`

, and
$\bot$ signifies `TRUE`

if the element
belongs in the set. But if an element does not belong in the set, we are
supposed to never terminate.
$\begin{aligned}
&0 \rightarrow \texttt{NO} \\
&0.\overline{9} \rightarrow \texttt{NO} \\
&1.00\dots \rightarrow \texttt{NO} \\
&1.a_1 a_2 \dots \rightarrow \texttt{YES} \\
&1.\overline{9} \rightarrow \texttt{NO} \\
&2.0 \rightarrow \texttt{NO} \\
&2.a_1 a_2 \rightarrow \texttt{NO}
\end{aligned}$

So, we can write a turing machine (ie, some code) that tries to decide whether
a real number $a$'s encoding $f_a$ belongs to the interval $I = (1, 2)$
as follows:
```
def decide_number_in_open_1_2(f):
# if the number is (1.abcd)
if f(0) == 1:
# (1.0...0<NOT0>) | look for the <NOT0>
# If the number is 1.00..., do not terminate.
if f(1) == 0: while f(i) == 0: i += 1
# (1.99...9<NOT9>) | look for the <NOT9>
# If the number is 1.99..., do not terminate.
if f(1) == 9: while f(i) == 9: i += 1
else: return
return
# if the number is not 1.abcd, do not terminate
while True: pass
```

Hence, we say that the interval $I = (1, 2)$ is - For every program $P$ which takes as inputs elements in $S$, the set ${halts(P) \equiv \\{ s \in S \vert P(s) \text{halts} \\}}$ is called as a
*semidecidable set*.

- Alternatively, we can say for a subset ${T \subset S}$, if there exists a program ${\hat T}$, such that ${s \in T \iff \hat T(s) \text{ halts}}$, then $T$ is semi-dedecidable.

```
def semidecide_empty(x):
while True: continue
```

The universe set is semi-decidable, due to the existence of the program:
```
def semidecide_univ(x): return
```

`A00, A01... A0n`

be the initial states of the machines. We are trying to
semidecide whether any of them halt. We lay out the steps of the machines
in an imaginary grid:
```
A00 A01 A02 ... A0n
A10 A11 A12 ... A1n
A20 A21 A22 ... A2n
Am0 Am1 Am2 ... Amn
```

For example, machine `A0`

has states:
```
A00 -> A10 -> .. -> Am0
```

We can walk through the combined state-space of the machines as:
```
A00
A01 A10
A02 A11 A20
A03 A12 A21 A30
...
```

Where on the `k`

'th line, we collect all states $A_{ij}$ such that $(i + j = k)$.
Now, if any of the machines have a state that is `HALT`

, we will reach the
state as we enumerate the diagonals, and the machine that explores the
combined state space can also return `HALT`

.
`machine_creator`

:
```
# creates a machine that stops after n steps
def machine_creator(n):
# f terminates after n steps
def f(x):
for _ in range(n):
continue
return
return f
```

We wish to check if the intersection of all `machine_creator(n)`

halt, for all
$n \geq 0, n \in \mathbb N$. Clearly, the answer is an infinite number of steps,
even though every single machine created by `machine_creator`

halts in a
finite number of steps.
- it relates to the order theoretic notion of downward closed set
- By yoneda , the downward closed set $(-\infty, r)$ contains the exact same order theoretic information as $r$ itself.
- It makes our "code" easier to write:

```
z = 10 # arbitrary fixed integer
def is_in_downward_closed_set(x_int, x_frac):
"""
return true if x_int.x_frac < z
"""
if x_int < z:
i = 0
while True:
elif x_frac[i] == 9: i += 1 # examine next number.
else: return True # x_frac[i] < r_frac[i]
else:
# loop forever
loop()
def loop(): while True: pass
```