Speaking computer science in mathematics

Question

Now I am writing a rather long monograph on the subject of computer science. Nevertheless, I am usually able to write a mathematical concept of mathematics, and it is difficult for me. For example, let's say I want to write a for-loop or void function. Most of the time I go to my Knut or Kormen or Sejuik, but now they are not enough. Is there a "guide" or some text that I can take as an example for translating computer science into mathematics?

EDIT: Let me be more specific (thanks, Uri). I mean: for example, I have a function that is invalid and returns a random string of length n. It aroused my curiosity, I don’t even know how to represent the void function in mathematics ... but again, this is just an example. I suffer from such issues. Thanks.

Answer 1

A summation or product designation can probably replace some for-loops. Others can probably be expressed as logical quantifiers (“There exists i such that a [i] has some property” or “a [i] has some property for all i”). (Sorry, I don't know how to do these in Markdown ... hope you get this idea.)

"Invalid functions" ... hmmm, maybe some convenient logical notation to indicate preconditions and postconditions, since such functions are only useful for their side effects?

But I think that most mathematicians will be familiar enough with the descriptions of the algorithms to understand any valid half-way pseudo-code convention. Just try to stay away from anything that requires the language-lawyer skill in any particular programming language.

Answer 2

I think you should be more specific. Are you talking about translation algorithms? Writing code as pseudocode?

There are many more “mathematical” formalisms, many of which are used in official verification of programs. They are usually based on discrete mathematics.

Depending on what you are trying to do, Hoare Logic is a good way to represent the steps of the algorithms, IMHO.

You can also formally specify some architectures and protocols using the Z notation .

Answer 3

To solve his specific question: in mathematics, if it takes no arguments and returns a random string of length n, it probably is not a function at all! That is, if f () is not equal to f () (for example, with f () = rand ()), then by definition f () is not a function. You can solve this in different ways, depending on your preferences: you can pass a status parameter to it and return the changed status parameter to it, or you can make it a multi-valued function and return all possible values, or you could use two functions: f ( n, state) gives the next random string of length n, and g (n, state) gives a new state after generating f (n, state).

Answer 4

You can see Programming Elements : Alexander Stepanov and Paul McJones:

This book uses the deductive method of programming through affiliate programs with abstract mathematical theory that allow them to work. The specification of these theories, algorithms written in terms of these theories, theorems and lemmas describing their properties are presented together. Implementing algorithms in a real programming language is central to the book. Although specifications that are addressed to people should, and should even combine rigor with proper informality, the code that is addressed to the computer must be absolutely accurate even while being shared.