Some days ago i've discovered that in most of what we call "models of computation ", we can possibly model tasks other than computation itself . For instance, in lambda calculus we can model control flow tasks ( modeling if, while, forif controls) with function applications, whereas in Turing Machines the control flow possibility is already embedded.

A couple hours ago, i discovered that we can model tasks other than computing and control flow with a Turing Machine . For instance, we can model the task of writing and reading data from a register ( the register actually becomes a region of the tape ) .

I have two questions.

1 - Are there any other important task other than computation ( as in calculation ) , control flow and reading/writing that can be modeled by "models of computation" ? Can all models of computation ( lambda calculus, u-recursive functions ) implement all those tasks ? For instance, can we model reading/writing of data not only with Turing Machines but also in lambda calculus ?

2 - I don't understand why we call all those models, "models of computation", when in fact they can model more than computation. Someone suggested to me that these tasks are all the same and should be all considered as "computation". But are these tasks really the same thing ? Can the kind of "computation" that we deal with in computability theory really be about control-flow and/or reading/writing of data ? Would it have any sense in talking about whether reading/writing data or doing control flow admits an algorithm ? It seems to me that the only real computation would be those tasks that when executed could provide information to us : solving a system of equations, finding whether a number is prime, calculating the best path between two points, finding the integral of a function, doing simple arithmetic or boolean logic .

In summary :

In the first question i wonder whether you can identify on the top of your head any other task, other than computation, control flow ( modelling an if,while,forif controls ) and reading/writing that can be modeled by models of computation, and whether Lambda Calculus can model reading/writing of data, just like a Turing Machine can.

In the second question, i wonder if there are any links between the tasks of calculating ( finding whether a number is prime, calculating the integral of a function ) , controlling flow ( implementing while,forif, if ) and reading/writing of data that is sufficient enough for us to consider all three of them simply as "computation".

Thanks a lot in advance.

  • 2
    $\begingroup$ I do not understand what you are asking $\endgroup$ – Trismegistos Jan 14 '15 at 16:34
  • 2
    $\begingroup$ @nerdy, on the other site I suggested that you should ask a specific question rather than "What do you guys think?" And here you see the response... Please reformulate your question to make it clear what the question is. $\endgroup$ – Andrej Bauer Jan 14 '15 at 20:13
  • $\begingroup$ Sorry. I just wanted opinions/answers on the two questions i posed. I edited the post, trying to be more specific. $\endgroup$ – nerdy Jan 15 '15 at 8:36