(0.999... = 1), which we'll see in detail in a moment.
TRUE, and signifies never halting at all !. So, the subset is semidedicable , in that, we will halt and say
TRUEif the element belongs in the set. But if an element does not belong in the set, we are supposed to never terminate.
Hence, we say that the interval is semi-decidable , since we have a function such that . We don't make any claim about what happens if . This is the essence of semidecidability: We can precisely state when elements in the set belong to the set, but not when they don't.
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
The universe set is semi-decidable, due to the existence of the program:
def semidecide_empty(x): while True: continue
def semidecide_univ(x): return
A00, A01... A0nbe 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:
For example, machine
A00 A01 A02 ... A0n A10 A11 A12 ... A1n A20 A21 A22 ... A2n Am0 Am1 Am2 ... Amn
We can walk through the combined state-space of the machines as:
A00 -> A10 -> .. -> Am0
Where on the
A00 A01 A10 A02 A11 A20 A03 A12 A21 A30 ...
k'th line, we collect all states such that . 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
We wish to check if the intersection of all
# 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
machine_creator(n)halt, for all . Clearly, the answer is an infinite number of steps, even though every single machine created by
machine_creatorhalts in a finite number of steps.
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