5
$\begingroup$

My question is very general, and the kind of answer I look for would be as low level as it could be. I think I may illustrate my query more succinctly with an example.

In propositional logic, you have the modus ponens rule which takes two hypothesis and asserts a conclusion. The hypothesis are stated as "static" pieces of code -they are just expressions, like the axioms of any theory; the same applies to the (detached) assertion. And finally, the rule itself is also a piece of code -and "static" in the sense loosely stated above. In essence, a computation using the modus ponens rule develops this way:

$\text{1) First Hypothesis: }\vdash {P}\ \\\text{2) Second Hypothesis: } \vdash P \rightarrow Q \\ \text{3) Rule Modus Ponens: }\vdash \{ \vdash P\vdash P\rightarrow Q \vdash Q\}\\ \text{4) Assertion: }\vdash {Q}$

In the example above I used the turnstile symbol to denote the notion of "provable" or "given".

Even though every step makes up a piece of code, something which could be equated to a string of bits in a memory tape ("static"), clearly between steps 3) and 4) the "detaching" of the assertion takes place. This action of detaching -the computation- appears as an irreducibly "dynamical" process, something which even if described by the four static written steps, constitutes a concept that seems not to be actually "captured" by them.

Extrapolating this sort of overly simplistic example, I feel troubled with the task of reconciliating both of the ideas of computation-as-an-object (for example, as a list of instructions to perform a given procedure, i.e. a computer program) and the notion of computation-as-an-action (the dynamical act of producing and spitting out the output, from the input data and the procedural rules).

Is there something I'm missing, misinterpreting, or plainly wrongly stating here?

  • 0
    Are you also troubled reconciling the notion of number-as-count ("I have 5 fingers") with the notion of number-as-action ("I multiply both sides by 5")?2012-08-29
  • 0
    Both the "counting" and the "action" are computational processes -there's a formal description to do both, for example in PA. The issue is in the relation between the "description" of the computation and the computation itself (the quotation marks emphasize the fact that I'm not sure the description captures the concept, or most probably I'm missing something).2012-08-29
  • 3
    A computation is an object, but it is not a list of instructions. The Turing machine is the list of instructions, and the sequence of instantaneous descriptions is the computation. (An instantaneous description describes the contents of the tape, the state the machine is in, and the location of the read/write head). Bt the way, I would describe modus ponens using $P,P\rightarrow Q\vdash Q$, or better with $P$ and $P\rightarrow Q$ on top of a line, and $Q$ below the line. Makes the analogy with program clearer.2012-08-29
  • 0
    You shouldn't place your Rule Modus Ponens on the same level as your Hypotheses. If you treat Modus Ponens as merely an hypothesis, the you would still need a Rule (indeed a form of Modus Ponens with _two_ hypotheses and an implication) in order to apply it to $P$ and $P\to Q$...2012-08-29
  • 0
    @MarcvanLeeuwen: I'd appreciate if you could elaborate more on the fundamental difference between hypothesis and rules of inference, which makes it wrong to "place them on the same level". I tend to view everything needed for a computation to be performed, as pieces of code -and the encoding in a bit-string applies equally to premises and rules, with the obvious differences in syntax, and nothing else- because that's how a computer program is written down to machine code; but then I get troubled with the concept of "change" associated to the computational process itself, from input to output.2012-08-29

3 Answers 3