Earlier quoted context omitted.
The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of a number. But are there other things that can be computed with a discrete and deterministic mechanism?" (At the time they called these "effective" functions.) Church had piles of stuff that he and his students produced that were computable with the lambda calc…
You seem like someone who might have a good book about this bit of history? Or perhaps a blog?
Turing Oversold?
231–240 of 311 posts
Re: Turing Oversold?
#232It's about being able to communicate it clearly. Being concise and presenting relatable models is important.
Results have limited value on their own. If they are not clear and concise you can't reach a wide audience.
Re: Turing Oversold?
#233Earlier quoted context omitted.
Exactly this. Unbounded doesn't mean infinite, and people are sometimes confused by the distinction.
Including me. What is the difference?
In a practical sense, turing machines don't voraciously consume tape. Adding extra feet of tape gives you an exponential increase in what you can compute. So if you set up a program to be reasonably judicious with its tape use, you can just say that if it reaches an end you pause it for a day, head to the shop, and buy another reel. Big computations take a lot of time anyway.
Re: Turing Oversold?
#234Earlier quoted context omitted.
I'm convinced that David Harland's Rekursiv[1:] machine _is_ the manner by which lambda et al. might be implemented at the machine level. Unfortunately, Rekursiv seems to have died an ignominious death, with the last Rekursiv chip having fallen off the side of a steamboat (apocrypha; I remember having read this, but I'm unable to find the original citation.) The Rekursiv advantage is its ability to do recursion on th…
I guess I'm confused as to why this is more than simply an interesting formalism. Complexity theory and models of computation are largely based around the Turing Machine model. Lambda calculus is an effective lens to design programming languages and prove equivalence between programs. We know by way of the Church-Turing Thesis that these two models are equivalent. The Turing Machine model is both better studied from…
I came into programming/computer science from a mathematics degree; I read some old treatises on recursion theory[1] and fell in love. I couldn't ever quite wrap my head around the Turing Machine formalism, but kept at it for a while. Finding Barendregt's paper [2] was a huge shock! I grasped it much quicker. So, yes, lambda calculus and the Turing Machine formalism are equivalent in explanatory power, but there are also reasons someone might prefer one to the other. So, yes, for me, the value _is_ the formalism.
As to why I think the Rekursiv would provide a good platform for implementing lambda calculus on the bare-metal, that's entirely due to Rekursiv's memory model advantage and the fact that it has a user-writable ISA. Why would someone choose to implement the lambda calculus on bare-metal? You call it "fetishism," I call it fun!
More generally, I just really like the idea of having a machine with a user-writable ISA.
[1] Theory of Recursive Functions and Effective Computability: https://openlibrary.org/books/OL2738948M/Theory_of_recursive...
[2] Introduction to Lambda Calculus: https://www.cse.chalmers.se/research/group/logic/TypesSS05/E...
Re: Turing Oversold?
#235Earlier quoted context omitted.
Exactly this. Unbounded doesn't mean infinite, and people are sometimes confused by the distinction.
Including me. What is the difference?
I think this is often part of the misunderstanding when you stumble into a post by someone who's confused about 0.999... = 1. People sometimes write things like: "0.999... only moves closer and closer to 1, it never reaches 1." I think that highlights a deeper point than people usually give these comments credit for. The thing is, 0.999... doesn't "move" anywhere, it's considered a completed object right from the beginning.
Anyway, the point is that Turing machines are not like this at all. They only look at a fixed-size part of the tape during each step, from this follows that they have only used a finite amount of tape at each point of their execution.
So for any given (halting) computation, you don't actually need an infinite tape, you just need "enough", without changing the result. This is important because it makes Turing machines a model for practical computers. For example, the device you're reading this on has gigabytes of tape, and that's big enough for many, many, many kinds of computation.
Re: Turing Oversold?
#236Earlier quoted context omitted.
I really enjoyed Stephen Wolfram's mini-bio of her. https://writings.stephenwolfram.com/2015/12/untangling-the-t... I very much recoginized from that that she had the attitude and experience of a "programmer," so I would say she was the first programmer, in the modern sense.
Wow, thanks for the link. Really interesting story, fascinating to think about what could have been if she hadn't died so young.
The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths. Its province is to assist us in making available what we are already acquainted with. This it is calculated to effect primarily and chiefly of course, through its executive faculties; but it is likely to exert an indirect and reciprocal influence on science itself in another manner. For, in so distributing and combining the truths and the formulæ of analysis, that they may become most easily and rapidly amenable to the mechanical combinations of the engine, the relations and the nature of many subjects in that science are necessarily thrown into new lights, and more profoundly investigated. This is a decidedly indirect, and a somewhat speculative, consequence of such an invention. It is however pretty evident, on general principles, that in devising for mathematical truths a new form in which to record and throw themselves out for actual use, views are likely to be induced, which should again react on the more theoretical phase of the subject. There are in all extensions of human power, or additions to human knowledge, various collateral influences, besides the main and primary object attained." -- Ada Lovelace, 1842 http://www.fourmilab.ch/babbage/sketch.html
Re: Turing Oversold?
#237Having an educational background in physics I find the Turing Machine a much more intuitive model of computation than say lambda calculus. To me this is Turing’s main contribution: linking the abstract world of computation to the physical world, and proving that a very simple physical machine can perform any computation (Turing completeness). That’s no small contribution.
> I find the Turing Machine a much more intuitive model of computation than say lambda calculus I think register machines are more intuitive than Turing machines - they are much closer to how real world computers work.
If you're trying to imagine something you can mechanically assemble out of discrete compoonents, it's not so great. You need an unlimited number of components hooked up in complicated ways.
A turing machine is a fixed-size and relatively simple box, plus a long tape that feeds through.
Re: Turing Oversold?
#238Earlier quoted context omitted.
Including me. What is the difference?
The usual difference is just predicate ordering -- (1) for every program there exists a tape big enough vs (2) there exists a tape big enough for every program. In the first case, each individual (valid) program can get by with a tape of _some_ fixed length, but there's no bound on how big that requisite length might be. In the second case, since the tape requirements can be arbitrarily high you would need a legitima…
Re: Turing Oversold?
#239Earlier quoted context omitted.
Likewise, people dispute that Ada Lovelace was the first programmer, because Babbage and Menabrea had previously created a few simple example programs. But that downplays her accomplishments too much. She didn't write the "first program" but she was the first to understand what computers would be capable of doing (for example, that by assigning numbers to letters and symbols, computers could do more than simply perfo…
Defining the first person to do anything is almost futile. No one exists in a vacuum and most first were standing on the shoulders of technological accomplishments far outside of their own field. That said, I'm sure in the case of Ada Lovelace there is at least some element of my misogyny involved.
Re: Turing Oversold?
#240Earlier quoted context omitted.
> Turing Machines, on the other hand, were instantly obviously mechanizable. It was clear that one could build a physical machine to run any Turing program without human input. Harold Abelson points out in one of his lectures [0] that computer science isn't about computers any more than biology is about microscopes. From that perspective, it is clear that Turing found an existing discipline of computer science and ma…
Computer Science is about what computers can do. To decide the latter, you have to first decide what a computer is. Turing Machines were the first abstractions that intuitively captured what it means to compute something
But it's certainly not the study of what mechanical computers can do. Among other things, mechanical computers all have bounded resources unlike Turing machines.