Recently, while I was looking for more sources of crossing sequence in computational complexity theory, I came across the article "Is Randomness 'Native' to Computer Scientist?" written by M. Ferbus-Zanda & S. Griogorieff. The writing style immediately caught my attention, since it's quite uncommon to me. Indeed, the whole article is written as a discussion between Quisani (Q), a fictitious student who asks questions, and the authors (A).

After a quick search, it seems that Yuri Gurevich was the first to introduce Quisani (as its virtual student). And interestingly, lots of Gurevich's coworkers (I guess?) adopt this style. Here are some instances :

I found this dialogue style very easy to follow, pleasant to read and sometimes even funny. In my opinion, this is a nice alternative to the usual format. But obviously it doesn't fit every author.

Here are some extracts:


(extract from Algorithms vs. Machines, Andreas Blass & Yuri Gurevich)

1 Prelude

Quisani: I have a question about the ASM thesis, the claim that every
         algorithm can be expressed, on its natural level of abstraction, by 
         an abstract state machine (ASM). Do you still believe this thesis?
Authors: Yes. In fact, there has been some recent progress [3], extending
         the proof from the sequential algorithms covered in [5] to 
         parallel algorithms.  To be precise, we deal with parallel algorithms 
         that operate in sequential time and have bounded sequentiality 
         within each step.

(extract from A New Zero-One Law and Strong Extension Axioms, Andreas Blass & Yuri Gurevich)

1 Shelah's Zero-One Law

Quisani: What are you doing, guys?
Author: We are proving a zero-one law which is due to Shelah.
Q: Didn't Shelah prove the law?
A: Oh yes, he proved it all right, and even wrote it down [14].
Q: So what is the problem? Can't you read his proof?
A: Reading Shelah's proofs may be research in its own right. His great 
   mathematical talent is not matched by his talent of exposition.
Q: I suspect that you don't limit yourself to reproving Shelah's theorem.
A: We have proved some related results [1].
Q: Tell me about this zero-one law which is exciting enough to divert your
   attention from abstract state machines.


(extract from Is Randomness 'Native' to Computer Scientist?, M. Ferbus-Zanda & S. Griogorieff")

6 Random Finite Strings and Their Applications

6.1 Random Versus How Much Random

Q: Let's go back to the question: "what is a random string?"

A: This is the interesting question, but this will not be the one we shall answer. We shall modestly consider the question: "To what extent is $x$ random?"

We know that $K(x) \le |x| + O(1)$. It is tempting to declare a string $x$ random if $K(x) \ge |x| - O(1)$. But what does it really mean? The $O(1)$ hides a constant. Let's explicit it.

Definition 15. [$c$-incompressible string] [...]

Q: Are there many $c$-incompressible strings?

A: Kolmogorov noticed that they are quite numerous.

Theorem 16. [...]


(extract from Is Randomness 'Native' to Computer Scientist?, M. Ferbus-Zanda & S. Griogorieff")

Q: Wow! It's getting late.
A: Hope you are not exhausted.
Q: I really enjoyed talking with you on such a topic.

(extract from Logic on words, Jean-Eric Pin)

Q: I am a bit tired, and I need to assimilate all what you said. What would
you suggest me to read?
A: There are several survey papers you could read [24, 26, 32, 29, 38, 48]. 
Then you can compulse the references given in these papers to go further on.
Q: Before I go, why did you get interested into logic?
A: [...]
Q: I see what you mean. It’s a good conclusion for our conversation. Thank you.

My questions are the following:

  1. Are there any authors (possibly in other fields) using a similar style or other alternatives?
  2. Any anecdotes of Quisani's born?

I would also want to know how the TCS community receive such writing style. Comments are welcomed.


A similar question is "Casual tours around proofs" which discuss "casual tour" style vs. "Definition-Theorem-Proof (DTP) format".


1 Answer 1


As far as I can know, Yuri's imaginary student Quizani (no typo, but the name was later changed to Quisani) was first introduced by Yuri in 1988. It was for his first Logic in Computer Science column of the Bulletin of EATCS. This column, entitled On Kolmogorov Machines And Related Issues ( Bull. EATCS, No. 35, June 1988, 71–82.) was later published by World Scientific Series in Computer Science, Current Trends in Theoretical Computer Science, pp. 225-234 (1993).

Here are the first sentences of this dialog:

It is often easier to explain oneself in a dialog. To this end, allow me to introduce my imaginary student Quizani.

  • Quizani: I think you should introduce yourself too. Don’t assume everyone knows you.

  • Author: All right. I grew up in the Soviet Union and started my career in the Ural University as an algebraist and self-taught logician. (...)

Later on, several authors, including myself, borrowed Quisani from Yuri to write their own columns. I still have Yuri's review of the first draft of my 1994 column: Yuri had criticized the fact that Quisani was a little too cooperating...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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