The Math Forum

Search All of the Math Forum:

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

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

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

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 ]

Posts: 51
Registered: 7/9/13
Effective method of getting a one-to-one onto function from a one-to-one

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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.