Lambda Calculus vs. Turing Machines (Theory of Computation) 

Thanks orki! I'm assuming you want more of an intuitive bridge than a formal proof. If so, consider that what you describe as "reduction" can instead be done as a "emulation". Instead of translating the representations, you can simply write a Turing machine emulator in lambda calculus and a lambda calculus evaluator as a Turing machine. Once this is done, any program in one tower can be run via the other tower. I find the above approach more satisfying than the formal proof which doesn't help my intuition.

@@AdvaitShinde thank you for the hint, you completely change my mindset about this question 🙂

@@AdvaitShinde for efficiency purposes though, wouldn't it be better to directly translate between the two?

​@@zyansheep there's two questions here: 1. Are Turing Machines and Lambda Calculus equivalently expressive (i.e. are there ideas in one that can't be expressed in another)? 2. What's the most efficient way to run a TM in LC or vice versa? #1 is addressed by emulation as discussed above (they're equivalently expressive - i.e. "Turing Complete"). #2 is more complicated. What does "efficient" mean? In what sense can you compare two TMs or LC programs and say one is more efficient than the other? Is it program size? Is it number of runtime steps? Is it amount of Turing Tape consumed (memory usage)? Is it runtime duration on an x86 machine (which is further just emulating a TM or LC interpreter)? Based on your definition of efficiency you get into all kinds of interesting sub-problems related to program optimization. In fact, this whole field of thinking is basically what you'd consider "compiler design". A complier is simply a program that converts code in one language into code in another language. As you can imagine, compiler optimization is a really deep topic that's outside the scope of this conversation but still completely understandable if you're interested. I would check out the many videos about it on RU-vid! All things considered, I'd encourage you to look beyond the idea that "efficiency" is a single/simple construct.

😂 I was hoping to not-so-subtly imply that the functional tower is better than the imperative one :)

Thanks Yui!

6 months later and i have finally internalized all that was said in this talk. now i’m neck deep in combinators due to a motivation in further reducing the axiomatic assumptions. So far, as far as i know, the most simplistic combinatory logic system can be built with the SK combinators which is a reduced version of the untyped lambda calculus. Thanks to this talk I was able to come at this with a conceptual map to orient my understanding! so thanks again!

Introduction to the Theory of Computation Textbook by Michael Sipser

@@nikhilsulghur7589 It doesnt talk about Lambda Calculus though

Hello! Perhaps you can send me more info about the problem you are facing?

@@AdvaitShinde so we develop two sorts of modifications for default Reduction Strategies (like the Left outer (Normal strategy) and the Right inner (reduce by data)): in the first sort we try to make reduction step by some assumption about depth of the redex in the tree term tree and the second one using reinforcement learning. And for some generated terms we couldn't see a much impact of the reduction strategy on the count of reductions (yeah, there are other metrics for measuring effectiveness, but it going to be the next step), so we suppose that there is no the universal optimal strategy (which give a minimal count of reductions for the all possible terms) with which we can compare an effectiveness of our algorithm and suppose expediency of all this modifications. So in other words our current problem: we couldn't find works (theoretical or practical) which prove that it is impossible or possible to create some sort of universal strategy which give the minimum count of reductions for any possible term.

@@v_donets Extremely interesting! Can you send me an email about your specific reduction strategies? I think I may have a proof for you to consider. Email is in my YT channel about page.

Nothing wrong with the models

There's a very interesting distinction here between a theoretical universal computer vs. an actual computer. Consider that the theoretical universal computers we discussed had no limits on input size (i.e. Lambda Calculus can handle arbitrarily long programs and Turning machines have an arbitrarily large tape). However, once we go and implement real computers, physical constraints impose limitations on our capacity to compute. Given any physical computer (arbitrarily large/complicated), there will always exist a finite limit with regards to its capacity to compute because of its physical limitations. Therefore, you can argue that any physical machine is not actually a universal computer because of these limits! Given this, humans aren't Turning machines. Moreover we've never actually built a Turing machine because Turning machines are entirely theoretical and are not buildable in the physical finite universe. All of this said, your question can be slightly rephrased and answered usefully: if you're ok with physical limitations on computation how can we judge humans and DNA/RNA with regards to their computational capability? It should be obvious that humans are general computers (within extremely modest constraints). These researches have gone on to describe (infinitely many) ways we can use DNA/RNA to compute things: arxiv.org/ftp/arxiv/papers/2008/2008.08814.pdf Considering the simplicity of lambda calculus (or even SK calculus which is mentioned in the paper and is even more simple) it shouldn't be too surprising that we can build physical and biological machines that are "universal" computers within their physical limitations. The fact that universal computation, at its most fundamental level, is actually extremely simple is perhaps the core thesis of this talk and an idea that continues to blow my mind every day.

@@AdvaitShinde Thank you ! It is very interesting indeed ! Have you read The revolutionary phenotype ? It’s about how the phenotype could become a replicator and subjugate the DNA.

I think your judgement of LC focusing on syntax over semantics is misguided. Think about LC from an axiomatic context where nothing is available for use without being explicitly denoted as an axiom. Here, LC has no concept of numbers or booleans - it *only* has functions. This might seem limiting but it turns out that booleans and the natural numbers can be defined in terms of functions! We don't need separate axiomatic structures for these concepts. This is similar to the fact that Peano didn't need to explicitly define the number 7 as it was defined as syntactic sugar for "S(S(S(S(S(S(S(0)))))))". Don't think about whether this is practically useful - nobody programs computers in LC. Instead think about LC as the minimum axiomatic definition for computing and consider how tiny of a definition it is for such a powerful concept! Finally I would absolutely include Shannon on a list with Turing, Godel, and Von Neumann!

Loops are an imperative construct and do not exist in the lambda world. Instead, anything that you would use a loop for can instead be expressed with recursion. As we discussed in the video, recursion can be obtained using the Y Combinator. So in a sense we can get loop-like functionality with Y but I wouldn’t describe that as “doing loops in Lambda calculus”. Hope that helps!