8 ms·
> The Church-Turing thesis is a statement about which functions of type `nat -> nat` are computable, either in the lambda calculus or using Turing machines. Th
by pron 10y ago
> The Church-Turing thesis is a statement about which functions of type `nat -> nat` are computable, either in the lambda calculus or using Turing machines.
This is how Krishnaswami frames things. From the TOC perspective, there is no such thing as functions at all. Computations consume and produce strings. Both Church and Turing explain how those strings can encode the natural numbers (there was no talk of types by either). Interpreting a computation as one computing functions on the natural numbers or any other set is an entirely interpretive activity that is external to the computation itself.
- nickpsecurity 10y agoIsn't the computation done with logical cells represented by a composition of boolean functions? And which are synthesized via functions sometimes from a functional language? What does this say about idea that, at ISA or abstract level, you're just doing computation if it's implemented as boolean, state machines. Note: Next step down are analog components that are basically specific functions on real numbers. That's what I got from studying analog computers anyway.
- pron 10y agoTuring personally addressed the question of analog computation and determined that they add nothing over discrete machines, as discrete computers can compute anything an analog computer would do to the desired precision that matters to you. He even discussed the subject in his 1936 paper, when he introduced his model. He wrote that eventually one would need to distinguish between two states, and so a model where states can be arbitrarily indistinguishable adds nothing, so you may as well discretize. When he wrote about the operation of the brain he said that it shouldn't matter if the brain is continuous or discrete; its operation could be simulated to arbitrary precision by a discrete process. He did wonder about quantum effects, though (he understood quantum entanglement when he was 16, Hodges writes).
- AnimalMuppet 10y agoBut isn't a computation that consumes and produces strings a function String -> String? (Or perhaps ordered_set<String> -> ordered_set<String>?) It also seems kind of ironic to have the functional programming people in the camp that says that there's no such things as functions...
- tome 10y agoHow 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#Statement_in_Church.27s_and_Turing.27s_words https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#S...
- pron 10y agoThey 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 and Turing themselves understood it. How would I define "anything"? As a function on any countable set -- the natural numbers, would do -- and I would explain what it mean to compute a function: pick a function, pick an input element, pick a finite representation for the input and output; if a physical machine can compute the output representation from the input representation, so can a universal computation model. I could choose a function between any two countable sets, e.g. (Nat -> Nat) -> (Nat -> Nat): pick a representation for the input and output and all models can compute the same functions, and those are the functions that machines can compute. They differ in abilities regarding representation within the model, but as the language models' representation require very significant computational work, I'd expect their representation to do more: they're paying for it. A C compiler works hard, so you'd expect it to provide you with a representation more suitable to your wishes than machine code. It's just that as a compiler like C translates a "meaningful" language to a machine encoding, everybody notices the work. The language "computation" models work in a vacuum, so I just pointed out that even though they don't translate anything from one representation to another, they still have to pay for their natural representation.
- kd0amg 10y agoa 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.
- catnaroek 10y ago> 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're syntactically different. This is the basis for compiler optimizations. And the lambda calculus (suitably extended with effectful computations) is better equipped than any machine model to make this identification. (OTOH, the lambda calculus is a grossly inadequate foundation for concurrency, which is about communication, rather than computation. The main solution I've seen proposed by proponents of functional languages, namely, abusing callCC to get something like cooperative concurrency, is very, very, very bad.) > Interpreting a computation as one computing functions on the natural numbers or any other set is an entirely interpretive activity that is external to the computation itself. In practice, people care about the meaning they ascribe to the symbols with which they compute. We use symbols to denote. A meaningless symbol might as well never have been computed at all.
- pron 10y ago> 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 price to pay. Machine models take bits and they compute bits, period. Like an apple that falls, they just do they're thing. If a person then wants to say, hmm, that apple's path describes an integral of acceleration, or I will assign the input and output bits mathematical objects, and say that the mapping is a function -- they're welcome to do it, but it's not what the computation does. > A meaningless symbol might as well never have been computed at all. Everyone agrees on that. But an apple that falls without Newton to grasp its meaning still falls, and a machine still computes. For meaning you have to pay real, measurable complexity. It therefore doesn't make any sense to compare a model that pays that price with one that doesn't.
- tome 10y ago> Computations consume and produce strings. Really? What's so special about strings? Perhaps I want computations to consume and produce trees. It seems like you've picked an arbitrary setting for computation and said "Look! My constructions which are naturally suited to this setting are naturally suited to this setting!".
- pron 10y agoLike entropy, computational/informational content is absolute. Strings have higher entropy. If I say, "I'll hand you a piece of fruit", that statement objectively has less information (and therefore smaller computational complexity to verify), then if I said, "I'll hand you an apple". A tree really is inherently more complex than a string. It's like an RNA molecule being more likely to be naturally synthesized in the primordial soup than, say, a cat. Of course, an unspecified "tree" could be as "entropic" as an unspecified string, but my guess is that you mean something more specific. So there's a real difference between various configurations of gas molecules in a box, and a real difference in the computational cost of representing them. Your statement is not unlike saying, "oh, so you've picked a high-entropy configuration, how convenient! What's so special about high entropy?" High entropy and low entropy aren't symmetrical. It takes more energy to move in one direction than the other. Again, you shouldn't be surprised by this at all (I'd think it's rather obvious). Since typed formulations do proof work in their validation step (that can be Turing-complete in some cases), obviously that means that there is more complexity in their representation, otherwise, you'd have computation for free. You can choose whatever representations you like. But representations that express more information, come at a higher computational cost.
- tome 10y ago> Again, you shouldn't be surprised by this at all (I'd think it's rather obvious). I'm not sure why you think that I'm surprised, or even why you think that I disagree with your overall argument. I'm just trying to help you build your argument by pointing out the most obvious aspects which need more careful elucidation. So your claim is that in the physical world strings are more fundamental than trees. Good to know. In fact I think there's an even simpler reason than the one you give of "entropy". That is, trees require space which grows exponentially in their depth, and thus they can't even be represented in the physical world.