3 ms·

OK, let me try. Consider the notion of an algorithm. You are probably familiar with an algorithm: a series of steps to be completed by a computer (aka a person

by chewxy 7y ago

OK, let me try. Consider the notion of an algorithm. You are probably familiar with an algorithm: a series of steps to be completed by a computer (aka a person). This is the launch point for what a Turing machine is. Turing asks the question: if there exists a machine that can slavishly follow instructions, what can such a machine do, and what can such a machine NOT do? To answer this question without invoking the AI problem, Turing started with the simplest possible set of objects to work with: binary numbers. A simple machine then would be a machine that reads a "tape" of binary numbers. The machine is simple, so it can only read one number at a time. Based on the number read, the machine may either move the tape left (reading the next number), move the tape right (read the previous number), replace the digit on the current cell, or halt. You can see why such a machine is considered simple: The range of inputs and the action space is VERY limited. And yet despite its simplicity, it's shown that such a simple machine can do addition. Specifically it can perform computation on recursively enumerable problems. It is in this very narrow and specific sense that Church's Lambda Calculus and Turing's machines are considered equivalent. Modern authors tend to extend the reach of Lambda Calculus, but you should bear in mind that the Church Turing thesis is valid only for functions N->N. That is to say if a Turing Machine can calculate the result of a function that takes a natural number and returns a natural number, lambda calculus can calculate the same result, and vice versa [sidenote]. Now, having a machine that can do all that is pretty cool. Ideally you'd want to be able to describe the rules of the machine. That's called a programming language. This notion really only formalized itself way after Turing died. Aho, Ulman and gang were really the ones who made the connection between languages and automata. Wang's B machine introduced the notion of abstraction in Turing machines by adding compound features that can be translated to simple Turing machines (for example, an instruction that would be "delete the value, and move right"). This led to the study of programming languages. The family of imperative programming languages are inspired by Turing machines in this manner. [Sidenote]: If only functions of N->N are comparable for the Church Turing thesis, then why do people generalize it to all kinds of functions? A cheap trick is to say, all functions can be Gödel-string encoded. A G-string is a huge natural number that represents a function. Thus if you can find the Gödelized function, then all functions are computable by both formalisms. I find this a bit distasteful - when we compute with CPUs we don't actually compute Gödel numbers!

verandacoffee 7y ago
> ... you should bear in mind that the Church Turing thesis is valid only for functions N->N This is not correct. The concept of algorithm has nothing intrinsic to do with natural numbers. You could use any data structure, e.g. finite strings of symbols from a fixed (per application) finite alphabet as is used in Post normal systems. The Lambda Calculus is also an example, as it doesn't use natural numbers, but its own expressions.
- chewxy 7y ago
  Church-Turing concerns computations not algorithms. The difference is subtle. A "computation" is what we would call a function application today - given an input, compute the output based on some rules. An "algorithm" is a set of such rules, usually operational rules (do this, then do this). The class of computations that Church and Turing are equivalent are the functions from N to N (encoding required obvs), as proven by Turing. Everything else is conjecture. Turing gives "computable by Turing machine", and Church gives "effectively calculable by the lambda calculus". Kleene holds them both to be the same, culminating in Theorem XXX. This misses a subtle point that this only applies up to the class of functions from N->N. When the class of functions is S->S, where S is a string or tree of symbols, lambda calculus runs into some minor issues. For example, you cannot define equality of terms in lambda calculus nor can lambda calculus realize itself. Bob Harper's book is the only book I know of that was explicit about this fact, though he dismisses it as a minor issue. Barendregt surprisingly also missed this.

by chewxy 7y ago

verandacoffee 7y ago

> ... you should bear in mind that the Church Turing thesis is valid only for functions N->N This is not correct. The concept of algorithm has nothing intrinsic to do with natural numbers. You could use any data structure, e.g. finite strings of symbols from a fixed (per application) finite alphabet as is used in Post normal systems. The Lambda Calculus is also an example, as it doesn't use natural numbers, but its own expressions.

chewxy 7y ago
Church-Turing concerns computations not algorithms. The difference is subtle. A "computation" is what we would call a function application today - given an input, compute the output based on some rules. An "algorithm" is a set of such rules, usually operational rules (do this, then do this). The class of computations that Church and Turing are equivalent are the functions from N to N (encoding required obvs), as proven by Turing. Everything else is conjecture. Turing gives "computable by Turing machine", and Church gives "effectively calculable by the lambda calculus". Kleene holds them both to be the same, culminating in Theorem XXX. This misses a subtle point that this only applies up to the class of functions from N->N. When the class of functions is S->S, where S is a string or tree of symbols, lambda calculus runs into some minor issues. For example, you cannot define equality of terms in lambda calculus nor can lambda calculus realize itself. Bob Harper's book is the only book I know of that was explicit about this fact, though he dismisses it as a minor issue. Barendregt surprisingly also missed this.