Enderton Computability Theory - Calculation of Semi-characteristic Function - Implicit Use of Infinity?

182 Views Asked by At

Enderton computability Theory (2011), p66 on kindle states :

Let K be the domain of the diagonal function K = {x | $[x](x) \downarrow$} ( with [x] being a register machine indexed by x, with input data (x) and $\downarrow$ means the machine halts and provides an output after a finite number of computational steps).

The semi-characteristic function of K : $c_K$(x) = 1 if x $\in$ K and $c_K$ = $\uparrow$ if x $\not \in$ K (where $\uparrow$ means undefined ie does not halt) is a register machine semi-computable partial function, ... because ... to compute $c_K$(x) we first try to compute $[x](x)$ ; if we succeed we give output 1, or in equation form

$c_K$(x) = 1 +0*$[x](x)$

(ie if $[x](x)$ is defined, then zero * $[x](x)$ = zero, so $c_K$(x)=1. If $[x](x)$ is undefined then $c_K$(x) is undefined).

My question is : how is it determined in a finite number of steps that $[x](x)$ is undefined - since the register machine $[x](x)$ result is only undefined if it does not halt, which can presumably in general only be known after an infinite number of steps ? If a matrix is set up, TestAllSteps(i,j), to test each register machine output for all possible computational steps i.e. $[i](i)$ (i=1,2..) vs the number of steps the machines are run for (j=1,2,...) and a suitable 1-1 ordering h(i,j) is made through the matrix, then its only when all finite values of h(i,j) have been tested that $c_K$(x) would be fully known. This would implicitly seem to assume that in some way all possible finite values can be tested, so looks like its using infinity.

1

There are 1 best solutions below

0
On BEST ANSWER

Henning Makholm response provides the answer - indeed infinity is used in computability theory :

Computability theory is about which functions can be computed in a finite number of steps. In order to speak about this we also sometimes need to define some functions or properties that are not computable; otherwise we wouldn't even be able to state that they're not computable. The property of "not terminating" is one of these