Is computation synonymous with functions in computer science?

[JonathanCollins]

Yes even in the case of hardware failure causing corruption to the variables generated by algorithms the end result is deterministic based on the exact sequence of events that occurred.

The wider and more interesting debate on this topic is the consideration of whether any event in the universe can be said to be random. If cause and effect can be pinpointed at the quantum level the entire universe becomes deterministic. Whilst observations of quantum particles appear to suggest random behaviour I am of the opinion that in time such observations will become explicable through an understanding of the mechanisms that drive such behaviour. After all at present there is to my knowledge no coherent model of the qualitative nature of any of the known forces (e.g. what actually causes 1 particle to be tightly bound to another in the nucleus of an atom?).

 

[Nidum]

Some random number generators have been built which derive their outputs by sampling physical phenomena .

Seen as a black box computer the input is the ON switch and the output is random numbers . ERNIE worked this way .

https://en.wikipedia.org/wiki/Premium_Bond

 

[Fooality]

Yes even in the case of hardware failure causing corruption to the variables generated by algorithms the end result is deterministic based on the exact sequence of events that occurred.

The wider and more interesting debate on this topic is the consideration of whether any event in the universe can be said to be random. If cause and effect can be pinpointed at the quantum level the entire universe becomes deterministic. Whilst observations of quantum particles appear to suggest random behaviour I am of the opinion that in time such observations will become explicable through an understanding of the mechanisms that drive such behaviour. After all at present there is to my knowledge no coherent model of the qualitative nature of any of the known forces (e.g. what actually causes 1 particle to be tightly bound to another in the nucleus of an atom?).

I think to have that conversation, one has to make clear: events in this universe are religiously deterministic if we believe the same complete state of system is always followed by the same following state, each time. Events in this universe are meaningfully deterministic if the same complete set of observables for a system is always followed by the same set of observables after it happens. The difference between the former and the latter is that in the former, we suppose a godlike all knowing observer who can determine the outcome knowing the current state but not us, and in the latter, WE can determine the outcome (or what we can observe of it) somehow from what we can observe from the current state.

I believe there's a parable in Islamic Hadith, that says in the beginning God told a pen to write the history of everything from the beginning till the end of time, and it did, and God has that transcript. That's the religiously deterministic universe, everything is predetermined, we just don't know what will happen, and never can. Its faith based, its rooted in the middle ages, and isn't useful for science. So that definition of determinism must be set aside.

That leaves us with the useful definition, where, when the set of observables available isn't sufficient to predict the set of observables that follow, you experience randomness, uncertainty about the outcome. Even if we do come up with a deterministic model of QM, it will still be there: There will be large, chaotic systems all the details of which are too large to fit into the largest computers of the future, and some elements will be unknown. Or, just take the Halting Problem from computer science. Computers are physical systems, so we should be able to determine, with our deterministic physics, whether any computer program will halt without running it, creating some crazy paradoxes.

So we will always have unknowns, always have randomness. The only alternative view is that of the omniscient viewer who won't tell us, which we have set aside.

edit: A word about observables: What this generation can observe, the last generation could not, so the set of things that can be determined is always growing, and science is in the business of growing it more and more. What's random is random precisely until it isn't... What we mustn't do is make the mistake of replacing the middle ages God with our present concept of our future selves..

 

[JonathanCollins]

Pity, I don't know rather it helps you, but all the computer could do is addition... Minus is plus with opposite sign, multiple is many times plus and division is many times minus. That's computer in real.

Actually at a fundamental level all a computer can do is represent binary 0 or 1

I think to have that conversation, one has to make clear: events in this universe are religiously deterministic if we believe the same complete state of system is always followed by the same following state, each time. Events in this universe are meaningfully deterministic if the same complete set of observables for a system is always followed by the same set of observables after it happens. The difference between the former and the latter is that in the former, we suppose a godlike all knowing observer who can determine the outcome knowing the current state but not us, and in the latter, WE can determine the outcome (or what we can observe of it) somehow from what we can observe from the current state.

I believe there's a parable in Islamic Hadith, that says in the beginning God told a pen to write the history of everything from the beginning till the end of time, and it did, and God has that transcript. That's the religiously deterministic universe, everything is predetermined, we just don't know what will happen, and never can. Its faith based, its rooted in the middle ages, and isn't useful for science. So that definition of determinism must be set aside.

That leaves us with the useful definition, where, when the set of observables available isn't sufficient to predict the set of observables that follow, you experience randomness, uncertainty about the outcome. Even if we do come up with a deterministic model of QM, it will still be there: There will be large, chaotic systems all the details of which are too large to fit into the largest computers of the future, and some elements will be unknown. Or, just take the Halting Problem from computer science. Computers are physical systems, so we should be able to determine, with our deterministic physics, whether any computer program will halt without running it, creating some crazy paradoxes.

So we will always have unknowns, always have randomness. The only alternative view is that of the omniscient viewer who won't tell us, which we have set aside.

edit: A word about observables: What this generation can observe, the last generation could not, so the set of things that can be determined is always growing, and science is in the business of growing it more and more. What's random is random precisely until it isn't... What we mustn't do is make the mistake of replacing the middle ages God with our present concept of our future selves..

It is feasible that a full understanding will be reached for all phenomena (including QM) at which stage the universe becomes deterministic, albeit still very complex in the same way that weather becomes increasingly deterministic as we gradually unravel the detailed variables. A future explanation to the apparent random behaviour of quantum particles may yet prove to be very simple; future computers may become exponentially powerful. There is no reason to suppose that something (however apparently chaotic) cannot ultimately be determined. What are the paradoxes to which you refer regarding computers?

W

 

[Boing3000]

Essentially, my question is, is the notion of computation wholly related to functions? Are the two terms somehow synonymously related?

It seems a lot of the answers have gone rogue on the recent hype revival of functional programming . But I would like to get back to your question.

First I think there is the same tension between Math and Physics then there is between Math and Computing/er. Each of those field trying to pretend ownership of the other.
I don't think that is the case. There is intersection between them, but some parts are clearly more distinct.

I think the reason is simple, both physics on computer have to handle "practical" rules and facts, that mathematics could probably describe, but to no ends.

In computing there is indeed "pure" function that would probably match pretty closely the math notion. Hence the same word is used. But where the math function is a mapping between input and output, a computer function is an instance of such a process that transform input into output.
I like to see the math as pure symbolism, and the computer function as a realization that would have to consume "energy". Its not pure, its not abstract, they could fail.
Even in its symbolic form, the computer function is deeply related with the fact that your CPU has a CALL / RET in its instruction set (that's why GPU are quite different to program).

So at one range of the spectrum, there is more pure function, like Add. Really, the pure functional language paradigm has a great deal of advantages, but they are often limited to handle the parts of the logic that is factually more close to pure math. SelectFirstElementOf(sequence) would be another example. But those function are not going anywhere. The purest math method I know of is the Mandelbrot set function. And really, it only gets its real beauty when computers take care of it. I really do think math an computing is the very same for all mathematics of iteration. I hope this will someday bring some new insight into the chaotics/fractal non-linear mathematics, that really need a revolution.

At the other end of the spectrum, there is the notion of process. There is a bunch of things (lets call them data), and those things will be peeked, poked, deleted, created, following a long range of procedure/recipe, producing along the way a lot of intermediate data. I don't think math could care less about [if then else]. But in every sense a computer only compute to compare and feed an "if" decision (lets be honest, its 99.9% of the time). I mean by that that computer are more like state machine, (which can also be describe/abstract by math) but is not linked to function/mapping. A browser is not a function. Its does not map the internet to page with url, even if some mathematician will pretend it is just what it does. What it does is follow a program, a procedure, it is only a bunch of: if then else and loop and or branch.
Instead of speaking of random() the paramount example of a function is open(). It is not math, it does does map close file to open file. But that method open a file. Call it twice, and your are dead meat (even one may fail). At this end of the spectrum I very much consider computing to be biology. Function are just strands of DNA proceed in semi chaotic orders putting some "life" into your machine.

Right in the middle of the spectrum, the is the notion of algorithm. Take quick sort for example. Is it a function that map a unsorted set to a sorted set ? Is it a slowly growing state change ? It is both, and it is at this interface of math and computing that I personally find the input of pure math the more important (I hope that mathematician do fell a symmetric feeling). I could also mention information theory and the ranking algorithm that everybody is so found of nowadays. Cryptography / compression is also at this middle range, in my views.

Well, back to work ;-)

 

[Jarvis323]

@Fooality, assuming randomness based on incomplete knowledge is no different than assuming a deterministic universe based on incomplete knowledge, it's an act of faith. Theoretical computer science doesn't take any such leaps, nothing is assumed except simple fundamental axioms. Everything is built from layers of logical/mathematical proofs. Talk about unknown input and such things may be a fun philosophical topic, but it really doesn't fit into theory of computing at all.

@Boing3000, the topic is not real computers, but theory of computation. This again is a pure math, and is almost entirely defined through set theory, and mathematical functions. Read about the Turing Machine or Lambda Calculus They are pretty much the foundations of computability theory.

The Church Turing Thesis essentially says that a Turing Machine can compute that which is computable. The question of the OP is essentially about the robustness of the Church Turing Thesis, considering the possibility that something which could be considered computation, but cannot be described through functions, could exist. This brings real computers into the picture, purely based on the idea that they can take analog signals, which introduces some question about the physical nature of the universe, and whether a non-deterministic universe could imply physical devices could compute something a Turing Machine cannot.

Of course trying to consider some chunk of text in the syntax of a programming language as a mathematical function, as written, is not going to always work. It doesn't even make sense to do. It's just text in a non-mathematical language that indirectly maps to some lower level instructions, that again gets mapped to lower level instructions, and then movements of electricity... Of course the fact that you can write some programming function who's signature doesn't look like a mathematical function, doesn't break the Church Turing Thesis. If turning over the long lived foundations of theoretical computer science was as easy as pointing to some arbitrary text based code, of for example a pseudo-random number generator, and saying look, it's not a function, then don't you think it would have been done long ago. Don't you think Turing and Church would have noticed and the Church Turing Thesis never had existed?

 

[FactChecker]

@Fooality, assuming randomness based on incomplete knowledge is no different than assuming a deterministic universe based on incomplete knowledge, it's an act of faith.

Don't argue with us. Argue with Heisenberg and his uncertainty principle. It is much more profound than many imagine. There is unavoidable random behavior in the physical world. Also. saying that something is deterministic, when you can not predict, repeat, or even explain the results afterword is a poor use of the word "deterministic". One can say that coin tosses are deterministic, but till there is a successful theory to explain and predict coin toss results, the word "random" is more fitting. And there are formal mathematical methods that can be applied.

That being said. Even with unknown inputs to a "computation", I agree that we can define the resulting computation as theoretically deterministic. That part is a function.

 

[Boing3000]

the topic is not real computers, but theory of computation.

I understand that its your understanding of the the question, and I disagree. The OP ask a about the relationship between the mathematical notion of function, and the computer notion of function. I have quote its sentences for a reason.

This again is a pure math, and is almost entirely defined through set theory, and mathematical functions.

Yes. Set theory is pure math. Nobody is questioning that. I am explaining that computer science is not pure math. I especially draw a connection with physics which is also not pure math. My intent is not to start a feud between mathematics and other field which deal "in logic" currency. There are also a lot of other field science filed, like medicine, geology. None of them is pure math either. Pure math is not an all encompassing ensemble. Pure math ensemble is big and full of treasure, and most of it is useless, as it should be.
Einstein equivalence principle is not part of math. It is physics.
x86 instruction set is not pure math. It is just a natural disaster ;-)

The question of the OP is essentially about the robustness of the Church Turing Thesis, considering the possibility that something which could be considered computation, but cannot be described through functions, could exist.

Listen I am not saying mathematical concept do not cross breed and enhance some part of some code. I have precisely stated the opposite.
But my take on "Church Turing Thesis" is that is is a case where actually it is the other way round.

This brings real computers into the picture, purely based on the idea that they can take analog signals, which introduces some question about the physical nature of the universe, and whether a non-deterministic universe could imply physical devices could compute something a Turing Machine cannot.

Wow. All this is surely interesting, and philosophical debates are funny (espacially in QM) but I'd like to keep my posting focused on the OP question, which is clearely not about "the nature of the universe"

Of course trying to consider some chunk of text in the syntax of a programming language as a mathematical function, as written, is not going to always work. It doesn't even make sense to do.

That's absolutely right. A very tinny percentage of the codes is written in mathematical language. Computing/er have its own domain, with a lot of different language and a lot of different sub domains/purpose (database, whatnot) ... as does have math and physics.

Don't you think Turing and Church would have noticed and the Church Turing Thesis never had existed?

I am quite confident that absolutely zero knowledge in pure mathematics is needed to build computers and the codes that they runs. I am not diminishing the importance of Turing's work. I just say they are complementary not opposite nor depending of each others.
It is just another kind of plumbing, more akin to car technology, than math. That's why teenagers can write code. No math degree is needed. And very few of my college have a bigger math level than I (that is: high school).
Computer science is more technology. Math is more theory. There is no conflict between them.

 

[Jarvis323]

@Boing3000, what I got out of that was that you know nothing about Theoretical Computer Science at all,did not understand the OP, and did not understand anything I said, but disagree with all of it. How do I respond to that?

@FactChecker, you can define things however you want. I believe the meanings I intended to be used for the terms random and deterministic, should have been clear from the context, and are not abnormal usage in the context. If you can wrap you head around the way I used the words enough to understand my arguments that's good enough for me.

 

[Boing3000]

@Boing3000, what I got out of that was that you know nothing about Theoretical Computer Science at all,did not understand the OP, and did not understand anything I said, but disagree with all of it. How do I respond to that?

Your are projecting too much. You are entitle to your interpretation of the OP question, and I also am. The only truth is that only the OP knows. Does that piece of logic is mathematically correct enough for you ?

I m not really into "Theoretical Computer", but contrary to your claims, I stated aver and over again, that it can be useful.
You've said d a lot of things that I agree on (even if not on the OP subject). But you also said things I disagree, and provide the reasons for my opinions.

If you are not interested to have a conversation (that is : without the childish "you don't understand"), just don't respond. It would be the logical thing to do.

 

[Dale]

Closed pending moderation.

 

[berkeman]

Thread has gone off track from the OP's question, so it will remain closed.