Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

On Two Views of Computation in Computer Science

pressron.wordpress.com

Post reply on HN
Print view View original

61–70 of 191 posts

Re: On Two Views of Computation in Computer Science

#61

Post by j2kun »

mathgenius wrote: post #55
Sniffnoy wrote: post #48

Earlier quoted context omitted.

I think you've got an interesting point, and I'd like to add to it a bit and refine/correct it a bit. First off, minor thing, but as Jeremy has pointed out, your terminology is wrong; "representation theory" means something else. You seem to mean something more like "model theory". But anyway -- I'm a mathematician, and I've noticed something like this too when I've dealt with physicists or their writings. But before…

> your terminology is wrong; "representation theory" means something else. You seem to mean something more like "model theory". I really do mean representation theory, in the widest sense of the word. Wide because I am trying to make connections here, not distinctions. So for instance, of course group representations. On the one hand there is an abstract group multiplication, and on the other side we are representing…

What you're describing sounds more like homology theory, where there is an abstract set of concepts (short exact sequences, etc.) which become different theorems in different contexts. But, unless I'm mistaken, most of the time these are closer to unifying foundations, or starting points, from which the special features of each model allow you to say more beyond the abstract framework. So sure you can get some general category-theoretic theorems, but saying the specific model is useless (as the Language folks say about Turing machines) is ludicrous.

Re: On Two Views of Computation in Computer Science

#62

Post by catnaroek »

pron wrote: post #58
catnaroek wrote: post #37

Earlier quoted context omitted.

> From the TOC perspective, there is no such thing as functions at all. I agree with you on this one. What actually exists in computing is procedures, which may or may not compute functions. For instance, even in Haskell, so-called “functions” may call `error` or diverge. However, it's very useful to treat extensionally equal procedures (considering both their effects and their final results) as equal, even if they'r…

> What actually exists in computing is procedures You can't free yourself from thinking in terms of languages :) Not a single one of the machine models -- TM, RAM, neural networks, DNA, digital circuits, quantum computers -- has a concept of a procedure. Procedures are language constructs. Whether you choose to compile Pascal or Haskell to x86 machine code is up to you, but in either case there would be a complexity…

> You can't free yourself from thinking in terms of languages

Now would I want to. Why would I deprive myself of the benefits of compositionality, separation of concerns, or simply modeling the problem domain as faithfully as possible?

> For meaning you have to pay real, measurable complexity.

Complexity in the sense of complexity theory? I don't see how. If you mean the computational cost of type checking, that's in practice a non-problem as long as the type system is reasonable. (By which I mean: Types are first-order and there is no type-level computation beyond synonym expansion, so plain first-order unification can reconstruct out all the types. Damas-Milner is a special case of this.)

Or are you talking about complexity in some other sense? I don't see the requirement of making sense as a burden. I'd feel burdened if I had to deal with some random computation I found in the wild, with no indication regarding what its meaning is.

Re: On Two Views of Computation in Computer Science

#63

Post by kd0amg »

pron wrote: post #56
tome wrote: post #31

Earlier quoted context omitted.

How then do you state the Church-Turing thesis? I note that the Wikipedia page claims that Church and Turing themselves used the word "function": https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#S...

They do use the word function, just not in terms of the language itself, but in the same sense of saying that a falling apple integrates the function from its mass to acceleration; it's a human interpretation of the encoding. I would state the Church-Turing thesis like so: a universal computation model can compute anything any physical machine can. As Hodges says in one of the links in the article, this is how Church…

a function between any two countable sets, e.g. (Nat -> Nat) -> (Nat -> Nat): pick a representation for the input and output

There isn't a TM-suitable representation for things of type (Nat -> Nat). No matter how you try to encode a Nat->Nat as a Nat (or a bitstring, if you prefer), you're going to screw up equality (which means you're actually encoding some other type). You'll map two unequal functions to the same Nat, or (more likely) map one function to multiple unequal Nats. This is the difference between how lambda calculi and Turing machines handle higher-order things: A Turing machine can always inspect the "internals," so you need an actual bijection from functions to strings, whereas lambda calculus hides the internals, so it's safe to map one function to multiple syntactic representations.

Re: On Two Views of Computation in Computer Science

#64

Post by ankurdhama »

The article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?

Re: On Two Views of Computation in Computer Science

#65

Post by catnaroek »

kd0amg wrote: post #63
pron wrote: post #56

Earlier quoted context omitted.

They do use the word function, just not in terms of the language itself, but in the same sense of saying that a falling apple integrates the function from its mass to acceleration; it's a human interpretation of the encoding. I would state the Church-Turing thesis like so: a universal computation model can compute anything any physical machine can. As Hodges says in one of the links in the article, this is how Church…

a function between any two countable sets, e.g. (Nat -> Nat) -> (Nat -> Nat): pick a representation for the input and output There isn't a TM-suitable representation for things of type (Nat -> Nat). No matter how you try to encode a Nat->Nat as a Nat (or a bitstring, if you prefer), you're going to screw up equality (which means you're actually encoding some other type ). You'll map two unequal functions to the same…

> so it's safe to map one function to multiple syntactic representations.

If the benefits of multiple representations of the same value aren't clear from this example, consider a more mundane one: red-black trees as representations of ordered sets. For obvious efficiency reasons, it's not desirable to assign to each ordered set a canonical red-black tree representation.

Re: On Two Views of Computation in Computer Science

#66

Post by kd0amg »

ankurdhama wrote: post #64

The article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?

It's a very impoverished form of composition if the only things you can really compose are the absolute primitives, rather than allowing you to compose things that are themselves composed. When you "program" with Turing machines, you don't have a way to take a section of "code" and paste it into another, larger program. You'll have to deal with two pieces numbering their states the same, overwriting each other's tape data, etc. If you have two Turing machines that solve separate pieces of the problem, you know there exists a single machine that does both things, but nobody actually goes and constructs that machine. Instead, they just mention its existence as justification for writing "do this; do that;" in a higher-level machine description.

Re: On Two Views of Computation in Computer Science

#67

Post by more_original »

ankurdhama wrote: post #64

The article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?

What he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a single program.

If the simple parts are given by machines, then in general there is no canonical way of composing them into a machine for the composed program. You have to construct a new machine from the machines for the parts. An example is the sequential composition of two functions with logarithmic space usage. You cannot just use run one machine after the other, but you have to modify both machines and then build a new machine that contains them in the right way.

Of course, one may use systematic constructions to combine simple machines into more complicated ones. But this amounts to the implementation of a programming model.

Re: On Two Views of Computation in Computer Science

#68

Post by ankurdhama »

kd0amg wrote: post #66
ankurdhama wrote: post #64

The article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?

It's a very impoverished form of composition if the only things you can really compose are the absolute primitives, rather than allowing you to compose things that are themselves composed. When you "program" with Turing machines, you don't have a way to take a section of "code" and paste it into another, larger program. You'll have to deal with two pieces numbering their states the same, overwriting each other's tape…

I think the problem can be defined as "Composition without isolation", each composed sequence of instruction has this same global context (all of memory) to work with which can lead to problems.

Re: On Two Views of Computation in Computer Science

#69

Post by ankurdhama »

more_original wrote: post #67
ankurdhama wrote: post #64

The article refers to one quora answer where the author says - "The machine-based models offer no notion of composition of programs from parts". The instructions are the parts of the so called machine model, isn't sequencing of those instructions and control flow instructions are nothing but composition?

What he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a single program. If the simple parts are given by machines, then in general there is no canonical way of composing them into a machine for the composed program. You have to construct a new machine from the machines for the parts. An example is the sequential composi…

I think you are confusing the word machine in this context. It is not the usual general purpose word machine that people use in every day life to denote a physical system. The word machine in context of model of computation means a specific type of "formal system" to describe computation. The problem of composition is about how this formal system does or doesn't support it.

Re: On Two Views of Computation in Computer Science

#70

Post by more_original »

ankurdhama wrote: post #69
more_original wrote: post #67

Earlier quoted context omitted.

What he means is that complicated programs can be built from simple parts. In programming languages you can just take simple parts and compose them into a single program. If the simple parts are given by machines, then in general there is no canonical way of composing them into a machine for the composed program. You have to construct a new machine from the machines for the parts. An example is the sequential composi…

I think you are confusing the word machine in this context. It is not the usual general purpose word machine that people use in every day life to denote a physical system. The word machine in context of model of computation means a specific type of "formal system" to describe computation. The problem of composition is about how this formal system does or doesn't support it.

No, I do mean formal machines like Turing Machines. Sequential composition of logarithmic space Turing Machines is a standard example for lack of compositionality.
Post reply on HN