0

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.

  • What makes you think it should be determinable in a finite number of steps that $x$ is undefined? – hmakholm left over Monica Oct 31 '16 at 11:45
  • @HenningMakholm : Thanks - though Isn't computability theory all about doing calculations in a finite number of steps using finite algorithms and not using completed infinities ? So to determine a semi-characteristic function fully should be done with a finite algorithm in a finite number of steps? Maybe there is a subtlety here I have missed - is there a reference that discusses the interplay between finite and infinite in computability ? –  Oct 31 '16 at 12:00
  • x @Colin: 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. – hmakholm left over Monica Oct 31 '16 at 12:16
  • @HenningMakholm: OK, so infinity is used after all. Computability Theory by Weber, page 55 says that partial functions / unbounded search is included because of Theorem 3.5.1 page 63 "There is no computable indexing of the total computable functions", i.e. even when using partial recursive functions. Presumably partiality is using logical expressions with unbounded "there exists" as the most simple form of infinite search to use ? So maybe the subtlety I missed was the reasoning behind why partial recursive functions are included in computability theory in the first place and its implications? –  Oct 31 '16 at 12:56
  • @HenningMakholm - I also just looked at The Annotated Turin - it describes Turins original paper - the definition of an algorithm there looks to be a finite set of instructions that can be executed infinitely often. All more subtle than I thought. –  Oct 31 '16 at 13:02

1 Answers1

1

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