6
$\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?

$\endgroup$
5
  • $\begingroup$ 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")? $\endgroup$ – Gerry Myerson Aug 29 '12 at 6:17
  • $\begingroup$ 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). $\endgroup$ – Mono Aug 29 '12 at 6:24
  • 3
    $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 29 '12 at 7:09
  • $\begingroup$ 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$... $\endgroup$ – Marc van Leeuwen Aug 29 '12 at 13:47
  • $\begingroup$ @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. $\endgroup$ – Mono Aug 29 '12 at 16:03
7
$\begingroup$

Perhaps the issue real here lie deeper, and indeed doesn't particularly concern computers. Get clear about the underlying general issue and the more specific puzzle about computers should evaporate.

In a paper in Mind in 1895 ("What the Tortoise said to Achilles"), long before the era of computers, Lewis Carroll already poses the same basic puzzle. So, suppose the Tortoise is given the premisses (i) $P$ and (ii) if $P$ then $Q$, but refuses to accept the conclusion $Q$.

You try to help him out, patiently explaining that (iii) if $P$ and if $P$ then $Q$ then $Q$. The Tortoise reponds, "OK, if you say so. I now accept (i), (ii), and (iii). But I still don't accept $Q$".

Well, you could offer him (iv) if $P$, and if $P$ then $Q$, and if $P$ and if $P$ then $Q$ then $Q$, then $Q$. The Tortoise, a cooperative fellow, says "You might be right. OK, I trust you. I'll accept premiss (iv) too. Now I've got four premisses. But what compels me to accept $Q$?"

You can see that giving the Tortoise yet another premiss isn't going to help!

What's the moral? We might put it this way: accepting a rule of inference like modus ponens should not be confused with accepting that a proposition like (iii). Or we can put it this way (as Gilbert Ryle did in a famous paper on Knowing How and Knowing That in 1948): knowing a rule of inference is a matter of knowing how to infer correctly, and that's knowing how to do something, which is different from knowing that something is the case, e.g. knowing that (i) and (ii) or indeed (iii) are true.

Not all knowledge is straightforwardly propositional knowledge; some is, as we might now say, procedural knowledge, knowledge about what to do. As the case of the poor Tortoise shows, getting more propositional knowledge doesn't in itself give you knowledge about what to do. And what goes for Tortoises goes for computers. Giving the computer more data isn't the same as teaching it to do stuff with the data. Feeding it the information that $P$ and that if P then Q is one thing; teaching it to draw inferences in something else. (That's why using the turnstile notation in setting up the problem both for assertions of data and for specification of a rule of inference is so horribly misleading.)

$\endgroup$
6
  • 1
    $\begingroup$ To clarify for myself the distinction between your two types of knowledge, is it similar to the distinction between a formal language and the model that you interpret it to be talking about? That is, are there two separate structures here connected by a map? And the Tortoise's "failure" is in his map? That is, he has the premises as propositions in his theory and has interpreted them so that they are associated to objects in his model. However, his map is not such that the relations among the propositions in the theory are carried over to relations among the objects in the model? $\endgroup$ – Rachel Aug 29 '12 at 23:00
  • $\begingroup$ I don't see why you assume the difference you state between "propositional knowledge" and "procedural knowledge" to be a clear concept. Eighty years ago it could have been a reasonable argument to say so, but with today's ubiquitous computer devices it clearly isn't. Any computer program is an example of "procedural knowledge" in your sense, and every copy of it is coded up as a bit sequence and is indistinguishably treated by the CPU just like any data set (some "propositional knowledge"). So, even though you correctly recongnized the rationale behind the question, you didn't answer it. $\endgroup$ – Mono Aug 30 '12 at 4:20
  • 1
    $\begingroup$ @Mono I'm not sure I was trying to answer the question, so much as offer some therapeutic remarks to massage away the temptation to ask it. If the way I put the point didn't work for you, so be it. But the point remains that as -- as Lewis Carroll's story long ago nicely shows up -- that there is a distinction to be drawn that is masked by your double use of the turnstile and your talk of what is "given" to cover both the data and the procedures for processing it. $\endgroup$ – Peter Smith Aug 30 '12 at 6:29
  • $\begingroup$ @Rachel The distinction between a formal syntax and a model for it can be thought of as a distinction between two things of the same type (structured objects), things which can stand in a certain relation. I was trying to mark a distinction that might better be thought of as a distinction between different types of thing -- the difference between axioms and rules of inference, and the corresponding difference between grasping an axiom and grasping a rule. $\endgroup$ – Peter Smith Aug 30 '12 at 8:27
  • $\begingroup$ @PeterSmith: what I try to point out is that your remarks are not evident, i.e. they don't simplify the issue by reference to simple and clearly recognizable concepts. If both sets of axioms ("propositional") and rules ("procedural") can be coded in a string of symbols and fed to a (physical) UTM -like any general purpose computer available today- which treats them equally as input (something "given" in the sense I used in my question), then the distinction you make isn't enough to make the question trivial and "massage away the temptation to ask it". Something else is going on here. $\endgroup$ – Mono Aug 30 '12 at 19:06
0
$\begingroup$

This is a bit off the cuff, so hopefully it won't get to wobbly.

The first step of defining computation is to fix a model. This is essentially what Church and Turing did with the $\lambda$-calculus and Turing Machines respectively. Being a certain flavour of computer scientist, I tend to think in terms of Turing Machines, so I'll reference them, but you can really stick any model of computation in (and there's no need to stick Church-Turing thesis in particular, i.e. we don't need at this point to know what truly encompasses all computation, just that there is some thing that does).

A Turing Machine (TM) is a collection of states with a transition function that describes what happens when certain input is encountered in each given state. It may or may not halt, it may be deterministic or not etc. Now I think the key point is that the TM is itself the computation. The description of what the TM does isn't, it's just a description.

Relating this to a computer and a program, the computer is (roughly) a universal TM, the program, where it able to run without the computer would be a TM, but when run on a computer is just input. It isn't the computation, the computation is the computer producing the output from the input.

In your examples, the list you give (depending on your perspective) is really a description of the "current" state of the computation at 4 given points. The computation is the process that with input passes through those states.

$\endgroup$
9
  • $\begingroup$ So, does that mean that what I call the "dynamical" component of computation (i.e. what makes it a process, rather than a set of ordered pairs of input and output elements) is a concept always placed at a meta-level from the point of view of the description of the computation (i.e. what I call the "static" component -the bit string which encodes the input and the deductive rules, such as the three first items I listed above)? Given that universality implies that any T-complete computer program can simulate any other program, might then the role of the TM be to lie at the metalevel? $\endgroup$ – Mono Aug 29 '12 at 15:33
  • $\begingroup$ Addon: I always felt uncomfortable when reading the description of a rule of inference, like MP, and finding that it always seemed to require the inclusion of symbols not included in the formalism to express it (like: "Hyp_1" & "Hyp_2" $\Rightarrow$ "Assertion", or equally, the "horizontal bar" which separates premises of the conclusion in natural deduction systems). Is this feature a consequence of the fact that the computation (following the rule description, i.e. it's code) is always performed by an instance of some computer model "outside" the formal system you're describing? $\endgroup$ – Mono Aug 29 '12 at 15:50
  • $\begingroup$ Yes, but I think I'd put it the other way. The "dynamic" part is the umm.. thing, and the "static" part is a meta-level description, where some bits are possibly abstracted ("for simplicity"). Though this might be more in the "whichever way makes sense to you" boat, as long as the distinction between a computation and its description is preserved (even if it is often blurred). When talking about universality, it gets more complicated of course. You have a UTM (again, sticking to TMs for no good reason), which is the computation, it happens to take as inputs descriptions of other TMs... $\endgroup$ – Luke Mathieson Aug 30 '12 at 1:12
  • $\begingroup$ which is not the same as the TMs themselves - a UTM doesn't take as input a bunch of states, a tape etc., it takes a string. As for it being "outside" the formalism, I guess it depends on what level you look at, it's certainly a bigger thing than its own transition function, which is what basically corresponds to the rules. $\endgroup$ – Luke Mathieson Aug 30 '12 at 1:14
  • $\begingroup$ I understand that universality guarantees that any two UTM's can simulate each other (i.e. given one machine of the pair, and the piece of code which describes the transition functions of the other one, the computations performed on arbitrary input would be indistinguishable from the computations corresponding to the actual running of the UTM being simulated, and viceversa). That's why I don't feel the necessity to state that "a TM desription is not the same as the TM itself", at least when the TM is T-complete (i.e. an UTM). $\endgroup$ – Mono Aug 30 '12 at 3:54
0
$\begingroup$

It seems to me that your confusion is because of not distinguishing between the execution (of an algorithm) with the code (of an algorithm).

An object like "a car" is different from an act performed by it like "driving a car".

$\endgroup$
1
  • 1
    $\begingroup$ It's not that I can't distinguish the concepts, my issue is accepting the fact that they cannot be "blended" together in any satisfactory way. For example, check the "Proof Explorer" presentation of the axioms of FOL as done by Norman Megill's Metamath site; the only two rules he introduces (MP and Gen) use symbols not included in the formalism presented. The whole idea of "having a closed description of a formalism" seems to fail as you always need an external input to perform the computation, i.e. the execution concept isn't self-contained. $\endgroup$ – Mono Sep 17 '12 at 15:48

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.