1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Notation meaning

  1. Nov 30, 2012 #1

    Can anybody tell me the meaning of

    f:N^n -->N
  2. jcsd
  3. Nov 30, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    It probably means a function whose domain is the n-dimensional set of natural numbers, and whose range is the (the 1-dimensional) set of natural numbers.
  4. Nov 30, 2012 #3
    What's an n-dimensional set? I think you mean the set of all n-tuples of natural numbers and the set of natural numbers itself, respectively.
  5. Nov 30, 2012 #4


    User Avatar
    Science Advisor

    Yes, that is what "n-dimensional" means here- the set of ordered n-tuples of natural numbers.
  6. Nov 30, 2012 #5
    Actually I was reading over Turing Machine, it was mentioned over there:

    For every function f: N^n -->N on the natural numbers, f is computable by an algorithm, f is computable by a Turing Machine.

    What does it mean?
  7. Nov 30, 2012 #6


    User Avatar
    Science Advisor

    It might be an attempt to state a version of the Church-Turing thesis. If so it is missing a piece. I would rewrite it as:

    "For every function f from N^n -> N, if f is computable by an algorithm then f is computable by a Turing machine"

    Clearly not every function from N^n to N is computable by a Turing machine; there are more such functions than there are Turing machines.
  8. Nov 30, 2012 #7
    Ok, understood.

    Well, I have one question. In the Church Turing thesis, what is meant by a function?

    Whatever we mean like y=f(x), in mathematics, is this a function?
  9. Nov 30, 2012 #8
    A function is what you wrote in your first post; it's mapping between sets (with some restrictions). "y=f(x)" is not a function, it's an equality.

    http://en.wikipedia.org/wiki/Function_(mathematics [Broken])
    Last edited by a moderator: May 6, 2017
  10. Nov 30, 2012 #9
    Ok, you mean to say bijection, injection and surjection?

    But when we say: y=f(x), in abbreviated form it becomes: f:X-->Y

    Then we make it in a set X (a,b,c) and another set Y (e,f,g) and try to show through mapping which elements map which one. Isn't it? But they are the same? Correct me if I am wrong.

    -- Shounak
  11. Dec 1, 2012 #10
    I an new to this subject. I was going over Church Turing thesis.

    There are certain concepts which I am unable to understand. If somebody can help me understand:

    The thesis states:'every effective calculable function is a computable function'.

    Now, here what does a function means? Is it the same as we know in mathematics as y=f(x)?

    The three ways of computability, the lambda calculus, Turing machine and recursive function define the same class of function. What is meant by that?

    Can anybody please help me?

    What is

    (a) primitive recursive function?
    (b) general recursive function


    -- Shounak
  12. Dec 1, 2012 #11


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    You are right. It was a vague, unconsidered statement of mine in need of your precision. Thanks, Michael. :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook