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

Turing Machines

samwho.dev

Post reply on HN
Print view View original

21–30 of 38 posts

Re: Turing Machines

#21

Post by samwho »

layer8 wrote: post #20
samwho wrote: post #17

Earlier quoted context omitted.

I’m not sure I understand. I do explain what can be computed, don’t I? > Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable. I could probably have dug into some of the restrictions, like how it has to be a finite number of steps.

This defines the term “computable”, but it doesn’t give you a sense of what things can be computed. Defining a term is entirely different from the above promise. At the level you’re describing Turing machines, it’s also not clear that readers would have a precise notion of what an algorithm is. At no point (unless I missed it) do you explain that any algorithm is supposed to be implementable as a Turing machine, or t…

That’s true, there’s no explicit definition of what an algorithm is. I may revisit this. Thank you for the feedback.

Re: Turing Machines

#22

Post by mithametacs »

zokier wrote: post #8

I'd argue the key difference between Turing machines and real-world computers is that computers do IO, respond to events, have real-time characteristics, and are interactive. All of these are key features in making computers useful, but are poorly (if at all) captured by Turing machine model. It's one thing to compute something, and another thing to play Doom.

I/O is just built on top of the tape. Real computers reserve a map of memory to I/O.

This is like saying a CPU isn't a computer. It's sort of right but sort of wrong, you know?

Re: Turing Machines

#24

Post by voidhorse »

layer8 wrote: post #10

> By the end of this post, you will know: > • What can and cannot be computed. I don’t think it delivered on the “can” part. (And I don’t think we really know that well.)

Unless I am missing something, as far as the work of Turing and Church is concerned, their answers are actually quite clear on this question of "can", namely the class of partial recursive functions. This is precisely what a Turing machine can compute. It is also possible to build up to these functions in a concrete way using the simpler class of primitive recursive functions. Rogers book on recursive functions and computability is a great reference on this topic.

Re: Turing Machines

#25

Post by fen11 »

> In 1936 both Alan Turing and Alonzo Church independently reached the conclusion, using different methods, that the answer is "no."

I think claiming these efforts were independent is misleading. Church was Turing’s PhD advisor in 1936, and one of the appendices of Turing’s thesis retroactively justifies the lambda calculus definition of computing, by proving it equivalent to his Turing machine definition. That sounds less like competing definitions of computability to me, and instead a story of collaboration to produce a philosophical justification (Turing machines) for Church’s pure mathematical theory (lambda calculus). Which is not to disparage Turing either: creating this philosophical justification was an impressive and fundamentally important achievement. I think Church sometimes gets unfairly maligned in these discussions as an out-of-touch purist who didn’t care to come up with a believable definition, but clearly he cared enough to support his student working on the problem!

Is there some evidence for the independence or competitiveness of their work that I’ve missed?

Anyway, apart from this nitpick about the introduction, I appreciate seeing this foundational stuff explained clearly!

Re: Turing Machines

#26

Post by bjornsing »

zokier wrote: post #8

I'd argue the key difference between Turing machines and real-world computers is that computers do IO, respond to events, have real-time characteristics, and are interactive. All of these are key features in making computers useful, but are poorly (if at all) captured by Turing machine model. It's one thing to compute something, and another thing to play Doom.

The key difference between Turing machines and real-world computers is that Turing machines have infinite memory. A real-world computer is thus not really a Turing machine, but rather a finite state machine.

Re: Turing Machines

#27

Post by jarpschop »

fen11 wrote: post #25

> In 1936 both Alan Turing and Alonzo Church independently reached the conclusion, using different methods, that the answer is "no." I think claiming these efforts were independent is misleading. Church was Turing’s PhD advisor in 1936, and one of the appendices of Turing’s thesis retroactively justifies the lambda calculus definition of computing, by proving it equivalent to his Turing machine definition. That sound…

I don't think Turing knew about the existence of the lambda calculus when he wrote the paper. It was later that he decided to study his PhD under Church and move to Princeton.

Re: Turing Machines

#28

Post by bubblyworld »

My favourite trivia about "On Computable Numbers" is that Alan Turing got the definition of computable reals wrong! The way he defines them - namely that a computable real is a Turing machine that generates the sequence of digits of the real - has severe issues, because addition and other basic operations are incomputable due to subtle diagonalisation arguments (see https://jdh.hamkins.org/alan-turing-on-computable-numbers/ for instance).

It's interesting that Turing didn't realise this, as the whole paper revolves around diagonalisation arguments in a few places.

The "modern" take is to define a computable real to be a program that takes an epsilon as input and returns a rational number within that epsilon from the real being represented. Or something similar - in this case it is very simple to define addition, for instance, as you have control over these bounds.

One more fact - equality is incomputable for both of these representations! There's no program that can uniformly decide whether two computable reals are the same, no matter how you cook up the definition. This one maybe isn't too surprising - in some sense no matter how many digits or bounds you check between two reals you can never be sure there isn't a smaller gap between them you haven't gotten to yet.

Re: Turing Machines

#29

Post by a57721 »

bubblyworld wrote: post #28

My favourite trivia about "On Computable Numbers" is that Alan Turing got the definition of computable reals wrong! The way he defines them - namely that a computable real is a Turing machine that generates the sequence of digits of the real - has severe issues, because addition and other basic operations are incomputable due to subtle diagonalisation arguments (see https://jdh.hamkins.org/alan-turing-on-computable-n…

Turing's definition of computable reals can't be wrong, because listing decimal digits is equivalent to giving rational approximations. The problem here is a confusion between real numbers and Turing machines that compute them.

Re: Turing Machines

#30

Post by qbane »

An essential point that the article did not address is that Turing machines can be efficiently encoded and be simulated by another Turing machine. This is the real power that causes the impossibility to solve its own halting problem.
Post reply on HN