Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Effective method of getting a one-to-one onto function from a one-to-one
function?

Replies: 4   Last Post: Sep 15, 2013 8:23 AM

 Messages: [ Previous | Next ]
 Sandy Posts: 51 Registered: 7/9/13
Effective method of getting a one-to-one onto function from a one-to-one
function?

Posted: Sep 13, 2013 8:02 AM

Suppose X is a set with aleph_0 members and f:X-->N is a one-to-one
function. Is there an effective (maybe even "canonical") method of
defining g:X-->N in terms of f so that g is one-to-one 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,new-state> 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 pre-assignable
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^{new-state}; 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 i-th prime and the q_i's are taken in their numerical order.

Date Subject Author
9/13/13 Sandy
9/13/13 Timothy Murphy
9/13/13 Sandy
9/14/13 William Elliot
9/15/13 Sandy