Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 4G (Automata and Formal Languages)

Fix an effective enumeration $f_{e,n}$ of the $n$-ary partial recursive functions.

The S-m-n theorem says that program inputs can be compiled into an index: for every $m,n\ge 1$ there is a total recursive $s_n^m$ such thatHere $\simeq$ means that either both sides are undefined or both are defined and equal.

The recursion theorem says that every total recursive transformation $h$ of program indices has a semantic fixed point: some $e$ satisfies

The Rice theorem says that every nontrivial extensional property of programs computed by partial recursive functions is undecidable.

By the S-m-n theorem, there is a total recursive function $h$ such thatfor all $x,y$. Apply the recursion theorem to $h$. It supplies an index $e$ for whichConsequently

Apply part (b) toThere is an index $m$ such that $f_{m,1}(y)\simeq g(m,y)$. Its domain of a partial function is exactlyTherefore

No. The propertyis extensional: it depends only on the partial function computed, not on its program index. It is nontrivial, since some partial recursive functions have a nine-element domain and others do not. The Rice theorem therefore implies that its index setis undecidable. Hence