Question: [11] It is important to distinguish between computable functions and the algorithms that compute those functions. To each function there correspond many different algorithms that
[11] It is important to distinguish between computable functions and the algorithms that compute those functions. To each function there correspond many different algorithms that compute it. Show that in the effective enumeration of Turing machines, as treated in this section, each partial computable function is computed by countably infinitely many different Turing machines. If T1, T2,...,Ti,... is an effective enumeration of Turing machines and Ti computes partial computable function φi, for all i, then each partial computable function f occurs infinitely many times in the list φ1, φ2,...,φi,... . This result is not an accident of our formalism and effective enumeration, but holds in general for all effective enumerations of algorithms that compute all partial computable functions.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
