3 ms·

What's wrong with thinking of such a relation as a "machine that takes in [a] value and gives you back another value"? This seems to me needless pedantry.

by Chinjut 12y ago

xamuel 12y ago
The machine could spit out different values when the same input was fed in different times.
Someone 12y ago
That machine can only handle computable functions (http://en.m.wikipedia.org/wiki/Computable_function http://en.m.wikipedia.org/wiki/Computable_function) Although many reasonable choices are equivalent, you should also be more precise in what you mean by 'a machine'. If your machine is a regular expression matcher, for example, it cannot determine whether an arbitrary string contains matching parentheses pairs (http://en.m.wikipedia.org/wiki/Chomsky_hierarchy http://en.m.wikipedia.org/wiki/Chomsky_hierarchy)
- pavelrub 12y ago
  "Machine" is an abstract term, not limited to Turing machines. Somebody who is just learning about functions has no understanding of what "computable" means, nor why should something be "uncomputable" according to some specific definition of a machine. We can invent in our minds all kinds of machines that don't exist in the real world: Oracle machines have existed in recursion theory since the time of Turing. If f is a function that tells us if a given Turing machine halts on a given input, there is nothing wrong about imagining this as a machine that receives a string and outputs a True/False answer. That no such machine can exist in the real world under some physical interpretation of the Church-Turing thesis is just a further observation - it has nothing to do with the correctness or usefulness of this formulation.
archibaldJ 12y ago
I think it is because we accidentally introduced the concept of time, which is a foreign concept to maths (but not to us), when talking about "machines" and the process of "taking [x] and giving you back [y]".
deleted 12y ago
[deleted]
anon4 12y ago
Nothing wrong per se - both definitions are right within their domains, i.e. programming¹ vs mathematics. It's just that I keep hearing (usually from FP people) how procedural/oo/impure functional/what have you programming languages should stop calling their functions functions, because they're not functions in the mathematical sense and therefore confusing; but I have the gut feeling that the programming definition (machine with input and output - X comes in, Y comes out) is the actually more intuitive one, and here we see someone explaining mathematical functions using the programming definition. Ultimately, I suspect that for computable functions, there is no difference between the definitions. So I found it interesting how here the "wrong/confusing" definition is used in place of the "correct" one. ¹ (edit) I mean programming as the engineering discipline of programming computing machines, not in the sense of discrete mathematics.

What's wrong with thinking of such a relation as a "machine that takes in [a] value and gives you back another value"? This seems to me needless pedantry.

by Chinjut 12y ago

What's wrong with thinking of such a relation as a "machine that takes in [a] value and gives you back another value"? This seems to me needless pedantry.

xamuel 12y ago

The machine could spit out different values when the same input was fed in different times.

Someone 12y ago

That machine can only handle computable functions (http://en.m.wikipedia.org/wiki/Computable_function http://en.m.wikipedia.org/wiki/Computable_function) Although many reasonable choices are equivalent, you should also be more precise in what you mean by 'a machine'. If your machine is a regular expression matcher, for example, it cannot determine whether an arbitrary string contains matching parentheses pairs (http://en.m.wikipedia.org/wiki/Chomsky_hierarchy http://en.m.wikipedia.org/wiki/Chomsky_hierarchy)

pavelrub 12y ago
"Machine" is an abstract term, not limited to Turing machines. Somebody who is just learning about functions has no understanding of what "computable" means, nor why should something be "uncomputable" according to some specific definition of a machine. We can invent in our minds all kinds of machines that don't exist in the real world: Oracle machines have existed in recursion theory since the time of Turing. If f is a function that tells us if a given Turing machine halts on a given input, there is nothing wrong about imagining this as a machine that receives a string and outputs a True/False answer. That no such machine can exist in the real world under some physical interpretation of the Church-Turing thesis is just a further observation - it has nothing to do with the correctness or usefulness of this formulation.

archibaldJ 12y ago

I think it is because we accidentally introduced the concept of time, which is a foreign concept to maths (but not to us), when talking about "machines" and the process of "taking [x] and giving you back [y]".

deleted 12y ago

[deleted]

anon4 12y ago

Nothing wrong per se - both definitions are right within their domains, i.e. programming¹ vs mathematics. It's just that I keep hearing (usually from FP people) how procedural/oo/impure functional/what have you programming languages should stop calling their functions functions, because they're not functions in the mathematical sense and therefore confusing; but I have the gut feeling that the programming definition (machine with input and output - X comes in, Y comes out) is the actually more intuitive one, and here we see someone explaining mathematical functions using the programming definition. Ultimately, I suspect that for computable functions, there is no difference between the definitions. So I found it interesting how here the "wrong/confusing" definition is used in place of the "correct" one. ¹ (edit) I mean programming as the engineering discipline of programming computing machines, not in the sense of discrete mathematics.