# Notation meaning

1. Nov 30, 2012

### shounakbhatta

Hello,

Can anybody tell me the meaning of

f:N^n -->N

2. Nov 30, 2012

### arildno

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.

3. Nov 30, 2012

### Michael Redei

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.

4. Nov 30, 2012

### HallsofIvy

Yes, that is what "n-dimensional" means here- the set of ordered n-tuples of natural numbers.

5. Nov 30, 2012

### shounakbhatta

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?

6. Nov 30, 2012

### jbriggs444

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.

7. Nov 30, 2012

### shounakbhatta

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?

8. Nov 30, 2012

### Number Nine

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
9. Nov 30, 2012

### shounakbhatta

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

10. Dec 1, 2012

### shounakbhatta

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?

What is

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

Thanks

-- Shounak

11. Dec 1, 2012

### arildno

You are right. It was a vague, unconsidered statement of mine in need of your precision. Thanks, Michael.