What is the Meaning of "f:N^n -->N"?

[shounakbhatta]

Hello,

Can anybody tell me the meaning of

f:N^n -->N

 

[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.

 

[Michael Redei]

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.

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.

 

[HallsofIvy]

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

 

[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?

 

[jbriggs444]

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?

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.

 

[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?

 

[Number Nine]

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?

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 )

 

[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

 

[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?

Can anybody please help me?

What is

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

Thanks

-- Shounak

 

[arildno]

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.

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