Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Turing Oversold?

people.idsia.ch

Post reply on HN
Print view View original

141–150 of 311 posts

Re: Turing Oversold?

#141

Post by ogogmad »

bsedlm wrote: post #138
ogogmad wrote: post #100

I need to find a reference for this: Goedel apparently believed that it was impossible to explicitly enumerate all the partial computable functions over the integers, until Turing proved him wrong. He reasoned as follows: - You can't enumerate the total functions because Cantor's diagonal argument is constructive. Given a claimed enumeration of N^N, you can perform Cantor's diagonal construction to produce a computab…

> The problem is that while a superset of an uncountable set is uncountable, a superset of a computably uncountable set may instead be computably countable. The partial functions over the integers show that this is indeed the case. > The computable countability of the partial maps from N to N. Can anybody give an example? does this have any to do with rationals? or is it more related to limits and calculus?

> does this have any to do with rationals? or is it more related to limits and calculus?

No.

I'm going to use Haskell, which I'm going to assume you know. I'm using it because it seems closer to the math. The type for naturals is:

data Nat = Zero | Succ Nat

and then all Haskell functions of type `Nat -> Nat` represent partial functions. They're not total functions because they might enter an infinite loop for some inputs. You can clearly enumerate all Haskell functions which are syntactically correct and which have type Nat->Nat, so the partial functions of that type are computably enumerable.

But consider the total functions of type Nat->Nat (i.e. those that never enter an infinite loop). Assume you can have a function `en :: Nat -> (Nat -> Nat)` which can output every total function of type Nat->Nat.

Then the function `counterexample n = Succ (en n n)` is a function that cannot be outputted by `en`, and therefore `en` fails to enumerate all total functions.

I've got other things to do, unfortunately, so I can't say more than this.

[edit] Fixed the counterexample.

Re: Turing Oversold?

#142

Post by tegeek »

If you take away all the media hype around Alan Turning and just see his contributions, he will still stand out.

On Computable Numbers [1] is perhaps one of the top 3 papers in the history of Mathematics. One of the most remarkable thing about Turning Machine is its simplicity.

Then again, in 1950, Can Machine Think[2] is perhaps the top 3 papers in the history of Philosophy. And then again, one of the most remarkable thing about Turing Test and the Imitation Game is its simplicity.

The impact of these two papers in the academia, industry and in our lives is huge.

Alan Turning is easily one of the top 3 Mathematicians and Philosophers of all time.

[1]. https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[2]. https://academic.oup.com/mind/article/LIX/236/433/986238

Re: Turing Oversold?

#143

Post by cma »

jgrahamc wrote: post #2

There's some confusion towards the end about Engima and Colossus: However, his greatest impact came probably through his contribution to cracking the Enigma code, used by the German military during the Second World War. He worked with Gordon Welchman at Bletchley Park in the UK. The famous code-breaking Colossus machine, however, was designed by Tommy Flowers (not by Turing). The British cryptographers built on earli…

> Yes, Turing worked on Enigma and the Bombe

Since it wasn't linked, Bombe was based on the Polish Bomba machine:

https://en.wikipedia.org/wiki/Bomba_(cryptography)

Re: Turing Oversold?

#144

Post by jimhefferon »

KingOfCoders wrote: post #117
bo1024 wrote: post #101

We've been over this. Gödel's mu-recursive functions were a poor model of computation because it's completely unclear how to physically implement the arbitrary-function minimization operator. So people didn't see how to build a machine that calculates this way. Similarly, there's no clear way how to mechanize lambda calculus. Turing Machines, on the other hand, were instantly obviously mechanizable. It was clear that…

"For example, it was claimed that Turing founded computer science.[...] Turing's 1936 paper provided the "theoretical backbone" for all computers to come." So your argument is, because it is unclear how to "physically implement the arbitrary-function minimization operator", Turing is the better "theoretical backbone" and has founded computer science?

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 calculus. Basically, all of the natural number functions that a person thinks are intuitively mechanically computable, those folks had showed how to lambda compute. With this evidence, he proposed to Godel (they were working together at Princeton at the time), who was considered the world's expert, taking "lambda-calculable" as a mathematically precise version of "mechanically computable." But Godel was notoriously careful, and he did not accept the thought as perfectly clear.

That is, they had a subset of the things that could be mechanically computed. But was it the entire set? Or was there something that some discrete and deterministic mechanism could be made to do that would lead to more than Church's set?

Imagine you are Dedekind and you are looking at the primitive recursive functions and (1) any such function is intuitively mechanically computable, and (2) you are able to work out how to define a pile of things like prime factorization of an integer using this system. You might well conjucture that this is it. But we know (and Godel and Church and Turing knew) that this is not it, that you need to add unbounded search of some kind (this is what minimization does) to get more things that are intuitively mechanically computable.

I agree that the minimization operator is not as easy to picture with gears and levers as some of the other operations. But the issue in 36 was that a person could worry that there was even more. Just as minimization is not as easy to picture and the need for it didn't hit Dedekind with great force, could there be something else out there that we have all missed?

That worry disappeared when Godel read Turing's masterful analysis. It convinced him that this is what a machine can do. He wrote, "That this really is the correct definition of mechanical computability was established beyond any doubt by Turing.'' Church felt the same way, writing that Turing machines have "the advantage of making the identification with effectiveness ... evident immediately.''

Re: Turing Oversold?

#145

Post by UncleMeat »

nzmsv wrote: post #95
simonh wrote: post #62

Earlier quoted context omitted.

I'm not advocating telling lies. Sometimes we simplify, and doing so can be perfectly appropriate. Unfortunately that does open the stage for nitpicking and pedantry.

Disagree. A finely crafted but ultimately false story can be actively harmful. A young person may think that they are not of the same caliber as "the greats" and cannot make their mark on a field, which would discourage them from trying. All the while in reality "the greats" were never as great as the historians later depicted them. "Come on in, collaborate, and make a difference" would be a much more positive messag…

This is where the humanities has the tech world beat. While we quibble over correct narratives and seek one option, the humanities has been completely soaked in the idea that there are nearly unlimited narratives that describe any given human endeavor and they weave together into a rich and ever-changing tapestry.

This is why a historian can read, understand (both the pros and the cons), and respect books that represent an economic history, a social history, an information history, a microhistory, and even a great-man history of a given subject without trouble.

More reason for engineers to take humanities courses!

Re: Turing Oversold?

#146

Post by wheaties »

tegeek wrote: post #142

If you take away all the media hype around Alan Turning and just see his contributions, he will still stand out. On Computable Numbers [1] is perhaps one of the top 3 papers in the history of Mathematics. One of the most remarkable thing about Turning Machine is its simplicity. Then again, in 1950, Can Machine Think[2] is perhaps the top 3 papers in the history of Philosophy. And then again, one of the most remarkabl…

Mathematicians? No. Computer Science? Yes.

If you want to group to math, you're going to have to compete with the likes of Euclid, Reiman, Bayes, Newton, Gauss, Cantor, Erdos, Fermat, Pascal, Leibniz, Bernoulli, Euler, Lagrange, Laplace, Fourier, Cauchy, Jacobi, Hamilton, Galois, Weierstrass, Cayley, Dedekind, Klein, Hilbert, Brouwer, Godel...

Re: Turing Oversold?

#147

Post by dralley »

bo1024 wrote: post #101

We've been over this. Gödel's mu-recursive functions were a poor model of computation because it's completely unclear how to physically implement the arbitrary-function minimization operator. So people didn't see how to build a machine that calculates this way. Similarly, there's no clear way how to mechanize lambda calculus. Turing Machines, on the other hand, were instantly obviously mechanizable. It was clear that…

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 perform numerical computations), and she was the first to invent foundational control flow structures such as loops and conditionals. Her program was much more rigorously defined and sophisticated than any previous examples.

>The longest program that Menabrea presented was 11 operations long and contained no loops or branches; Lovelace’s program contains 25 operations and a nested loop (and thus branching).

https://twobithistory.org/2018/08/18/ada-lovelace-note-g.htm...

https://writings.stephenwolfram.com/2015/12/untangling-the-t...

https://projectlovelace.net/static_prod/img/Diagram_for_the_...

Re: Turing Oversold?

#148

Post by [deleted] »

codeflo wrote: post #19

It seems to be in style now to try to tear down the public perception of past great minds, I recently read a similar article about Hawking. And while this article may have some points, I don't think the overall framing is fair. I think everyone with an interest in theoretical CS should work through Turing's 1936 paper at one point in their life. For me, the important part of that paper is how convincingly it argues t…

[deleted]

Re: Turing Oversold?

#149

Post by jmull »

Well, this article certainly shoots itself right in the foot.

If the problem is that some important early contributions to CS are being overlooked, the solution is to promote those contributions.

By framing this as Turing vs. others, the focus is squarely on Turning and his contributions. It puts itself in the position of having to beat down and minimize Turing’s contributions before raising up other contributions. Pretty much setting itself up to fail to convince very many.

Instead, e.g., present the narrative of those early contributions, showing how they provided the foundation Turing worked from.

(edit: I should add: I understand perfectly that the point of this article probably isn’t to actually convince anyone of anything, but is just a hot take meant to get people worked up for the page views. So mission accomplished, from that perspective, I guess.)

Re: Turing Oversold?

#150

Post by UncleMeat »

legostormtroopr wrote: post #80
OskarS wrote: post #56

Earlier quoted context omitted.

> But if you need to choose a Founding Father of Computing Science for the general public, I'd say Alan Turing is the best candidate. Scholars will give due credit to Church, Zuse, von Neumann and all the others. I agree with this. It's certainly the case that I wish more people knew of Alonso Church and Kurt Gödel, but you have to realize in a "PR" sense that it's simply not going to be feasible to teach the general…

> The fact that he was shamed into suicide is just all the more reason to celebrate him now. Please don’t diminish his legacy by repeating this lie. Turings suicide is contentious and circumstantial at best. His documented behaviour had none of the very common signs of suicide - there was no note, he had plans for later in the week, and none of his close friends noted any change in behaviour.

Suicide or not, his treatment by society was equally heinous and repulsive. Even he had lived a complete and happy life, his story would have been a bright example of the terror and evil of homophobia.
Post reply on HN