Live data from Hacker News

Turing Oversold?

people.idsia.ch

231–240 of 311 posts

Re: Turing Oversold?

#231

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?

About the Theory of Computation in general. A draft: https://hefferon.net/computation/index.html :-)

Re: Turing Oversold?

#232
It's not necessarily about being the first to discover a result.

It'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?

#233

Earlier 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 theoretical sense, an unbounded number is always finite.

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?

#234

Earlier 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…

For me, personally, I really like the lambda calculus as a tool to organize and better my computational thinking.

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?

#235

Earlier quoted context omitted.

Exactly this. Unbounded doesn't mean infinite, and people are sometimes confused by the distinction.

Including me. What is the difference?

Some parts of mathematics deal with infinite sequences, that is, actually infinite lists of numbers. It's usually assumed, and important for analysis, that these numbers are considered to be "all there" right from the beginning. You can do operations like: Compute the limit. Add up all of its elements. Determine whether two sequences are identical for all entries after the trillionth.

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?

#236
post #178
post #154

Earlier 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.

"It is desirable to guard against the possibility of exaggerated ideas that might arise as to the powers of the Analytical Engine. In considering any new subject, there is frequently a tendency, first, to overrate what we find to be already interesting or remarkable; and, secondly, by a sort of natural reaction, to undervalue the true state of the case, when we do discover that our notions have surpassed those that were really tenable.

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?

#237

Having 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.

In the days where you can buy a ram chip, a register machine is a really easy abstraction.

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?

#238
post #210

Earlier 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…

Note that tape usage typically depends on the input, so I would distinguish programs and computations (program + input).

Re: Turing Oversold?

#239

Earlier 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.

Awkward typo.

Re: Turing Oversold?

#240

Earlier 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

Sure, if you take "computer" to mean "something that computes". In that case it would include humans. There was a great deal of research into things that can be effectively computed that goes back even before the focus of this article. And of course "computer" used to refer to humans who computed before the invention of mechanical computers.

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.

Post reply on HN