Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.