1
$\begingroup$

I want to be able to represent a set of operations in sequential order such that they will represent what is traditionally called a "function" (which is not always the mathematical definition of a "function"). However, I'm trying to define more primitive terms:

  • object - Anything that can be manipulated throughout the course of a program; that is, they can be read and set.
    • place - A container that can hold value. (e.g. variables)
    • value - A value. (e.g. 2+2 is a value but not a variable).
  • procedure - A sequence of operations.

I want to be able to define procedure in more definite terms. Note that I will be starting without the definitions of operations, as I want to be able to define basic operations as procedures.

I know that I may want to introduce the sense of "time" and "space" for programs, time being necessary due to the definition of "sequence" that I put forth. Is there a better way to define it? Is there already work out there that explores this?

How would you formally define a procedure or operation at its most basic level?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Have you looked at existing models of computation, like μ-recursive functions or RAM? $\endgroup$
    – svick
    Feb 21, 2016 at 11:13
  • $\begingroup$ You could try en.wikipedia.org/wiki/… . This defines a program in terms of transitions between states. So, your sequence points would be the transitions. $\endgroup$
    – wvxvw
    Feb 21, 2016 at 16:35
  • $\begingroup$ @svick Yes; I've taken a bit of a look at mu-recursive and RAM; both doesn't seem to implicitly consider the notions of time as a fundamental aspect of the system or consider space as a fundamental aspect of the system. I think that RAM is probably the closest to what I want to use; however, I want to create an abstraction that might be more general than RAM. $\endgroup$
    – CinchBlue
    Feb 22, 2016 at 4:16
  • $\begingroup$ @VermillionAzure RAM does consider time: you can count how many instructions were executed. Space is there too: you can count how many registers were used, but it may not be a good measure, since every register can store arbitrary integer (i.e. is infinitely large). $\endgroup$
    – svick
    Feb 22, 2016 at 4:29
  • $\begingroup$ @svick I would say that the model's register size should be a parameter of the model, not inherent to it. Additionally, a RAM may not be able to handle the mutations of its registers by more than one algorithm running at the same time. Such systems are important for modeling multithreading, etc. $\endgroup$
    – CinchBlue
    Feb 22, 2016 at 4:40

1 Answer 1

Reset to default
1
$\begingroup$

Take a look at Gurevich's abstract state machines. See also the abstract state machine homepage. A key paper is Gurevich's Sequential Abstract State Machines Capture Sequential Algorithms.

Improve this answer
$\endgroup$
3
  • $\begingroup$ From what I understand, is there an effort to capture the difference between place and value? $\endgroup$
    – CinchBlue
    Feb 22, 2016 at 5:59
  • $\begingroup$ This is a philosophical question, which is unfortunately beyond my expertise. $\endgroup$
    – Yuval Filmus
    Feb 22, 2016 at 6:00
  • $\begingroup$ There is a very important distinction between vehicles of information and information itself, as well as what actually constitutes information. Given that most computers have finite vehicles in which to hold information, and that such vehicles can be occupied by different information with respect to time, I would consider that the creation of a model would be best. $\endgroup$
    – CinchBlue
    Feb 22, 2016 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.