Sandy
Posts:
40
Registered:
7/9/13


Effective method of getting a onetoone onto function from a onetoone function?
Posted:
Sep 13, 2013 8:02 AM


Suppose X is a set with aleph_0 members and f:X>N is a onetoone function. Is there an effective (maybe even "canonical") method of defining g:X>N in terms of f so that g is onetoone and onto?
Background: X is a set of Turing machine programs and f is a Gödel numbering. What I want is an invertible Gödel numbering.
So, X is a countable set of finite sets of quadruples <state,symbol,action,newstate> and maybe someone knows an invertible g straight off without me having to frig an existing f. But uniformity would be nice, that is to say if the number of states and the alphabet of symbols changes, it would be nice if the definition of g stayed the same. Producing a uniform f is not a problem:
Call the states 1, 3, 5, ... (a finite no. but with no preassignable upper bound); the symbols 6, 8, 10, ... (ditto); the actions 2, 4, 6, ... (ditto). So 2 and 4 are L and R respectively, and action y > 4 is "print symbol y".
Then the Gödel number of a quad is q_i = 2^{state}*3^{symbol}*5^{action}*7^{newstate}; and the Gödel number of a program P (= set of numbers q_i) is product_{q_i in P}p_i^{q_i} where p_i is the ith prime and the q_i's are taken in their numerical order.

