Donate SIGN UP

Parametrization - S-M-N Theorem

Avatar Image
Peter Pedant | 09:37 Sun 21st Oct 2018 | Science
5 Answers
if you have a partial computable function

f(x,y) = y if x is even
and is undefined otherwise

that is f is a partial computable function

then the s-m-n theorem guarantees there is always a totally computable one placed function
gx of (y) which is total - - x is an computable index

what happens to the undefined cases ? in f where do they go to in g ?

suppose f is undefined everywhere - what does g look like ?

( yeah reading Cutland ) thanks
yeah a serious science q for a change
Gravatar

Answers

1 to 5 of 5rss feed

Best Answer

No best answer has yet been selected by Peter Pedant. Once a best answer has been selected, it will be shown here.

For more on marking an answer as the "Best Answer", please visit our FAQ.
I'm nervous about answering something like this when I don't actually know, but as far as I can see the result only applies to the computable cases of f(x,y). Therefore, if it's undefined (or uncomputable) everywhere, no such g exists. That's my intuition, anyway.
Question Author
Thx J
I might write to Cutland -
if a BA in Maff (er you)- soon to be PhD says good q
then I can take it forward

and yeah - this is an abnormal question on Science as I havent asked why Pi isnt fwee ( much easier to calculate) or was Darwin a roman cafflic ( no he wasnt)
Echoing Jim here, as I never studied this part of number theory, but in the first line you define the function,

f(x,y) = y if x is even and is undefined otherwise

You then ask a question that appears to contradict the original definition:

"suppose f is undefined everywhere - what does g look like ? "

So the question is (in mathematical terms) meaningless. Something like "How many volts does an apple weigh?"

Which, is, I think what Jim said, but expressed in different terms.

Not sure this is really one for Answerbank - maybe for a specialist number theory community, like this one:

https://math.stackexchange.com/questions/1679179/problems-understanding-proof-of-s-m-n-theorem-using-church-turing-thesis
Question Author
oh yes no
thanks for the cont
one f but two functions
f being even and otherwise undefined
and then suppose - another f ( I should have said h ) where it is undefined everywhere

The stack exchange question is good
thanks - the problem ( remember there could be more than one problem in this question ) being that I understood the stacker didnt.

f( x,y) goes to Φg(x)(y) ( smn theorem )
by writing a program where you whack fixed x into register no 1 of a tm doing f and move all the other registers forward one.
The godel no of this program is g(x) and so it is effectively computable

IN fact on thinking about it ( what happens to the undefined cases of f(x,y) so with x =3 - suppose it is print y if y=3n for some n and otherwise undefined

then Φg(x)(y) the domain is 1,2,3,4 and the range is 3,6,9,12
and hey presto Φg(x)(y) is a total computable function

[ compatible with a later result - an r.e. set is the range of a total computable unary increasing function]

Question Author
// So the question is (in mathematical terms) meaningless. Something like "How many volts does an apple weigh?" //

erm - well I have never found the 'answer'
"your question isnt a question so I dont have to answer it"
very useful ( to the questioner)

1 to 5 of 5rss feed

Do you know the answer?

Parametrization - S-M-N Theorem

Answer Question >>

Related Questions

Sorry, we can't find any related questions. Try using the search bar at the top of the page to search for some keywords, or choose a topic and submit your own question.