Turing and Godel

Presumably, most here are familiar with the concept of undecidability.

My question is simple, though perhaps not the answer: Godel published 
his results first, hence does Turing's non-computability theorem 
(the halting problem), follow as a corollary?  What is the relationship 
between these seemingly parallel theorems?

--
Rich

RichD wrote:
> Presumably, most here are familiar with the concept of undecidability.
>
> My question is simple, though perhaps not the answer: Godel published
> his results first, hence does Turing's non-computability theorem
> (the halting problem), follow as a corollary?  What is the relationship
> between these seemingly parallel theorems?
>

I'm pretty sure Turing used Godel as part of his design of The Halting 
Problem. It could effectively be considered a restatement of it.

There's little parallel about them; they're statements of the same basic 
problem. At some level, they're quite different, at
another they are exactly the same.

The Turing version depends on the reliable productivity of
a tape factory, somewhere.

Of course, historically, the great cosmic joke is that Godel
( who was nominally German ) was an unwitting accomplice to
the efforts of Bletchley Park in breaking Enigma.

I am very sure you cannot make stuff like that up. But phrased
properly. the joke is:

My dog has no nose.
How does he smell?
Awful.

> --
> Rich
>

--
Les Cargill

On 2016-01-23 05:02, RichD wrote:
> Presumably, most here are familiar with the concept of undecidability.
> 
> My question is simple, though perhaps not the answer: Godel published 
> his results first, hence does Turing's non-computability theorem 
> (the halting problem), follow as a corollary?  What is the relationship 
> between these seemingly parallel theorems?

You might think the Turing statement as an
application, for the Turing Machines, of
the Godel's results.

bye,

-- 

piergiorgio

On January 23, Piergiorgio Sartor wrote:
> > My question is simple, though perhaps not the answer: Godel published 
> > his results first, hence does Turing's non-computability theorem 
> > (the halting problem), follow as a corollary?  What is the relationship 
> > between these seemingly parallel theorems?
> 
> You might think the Turing statement as an
> application, for the Turing Machines, of
> the Godel's results.

yes, something like:
Godel:  "Undecidable propositions exist."
Turing:  "And here's one..."

But still, I'd like to see a more direct path from A to B, because 
if you look at their papers, they're talking different languages.


--
Rich

On Sun, 24 Jan 2016 18:42:15 -0800, RichD wrote:

> But still, I'd like to see a more direct path from A to B, because if you
> look at their papers, they're talking different languages.

If the only form of repetition which a program uses is a classical "for"
loop (where then number of iterations is fixed in advance), then clearly
the program will terminate eventually.

The hard case (in terms of any practical attempt at deciding termination)
is the use of "while (<predicate>) { do_stuff(); }". Determining whether
the loop will terminate boils down to determining whether the predicate
will eventually become false. So the general case of deciding termination
(Turing's problem) boils down to a decision procedure for predicate logic
(Goedel's problem).

Les Cargill <lcargill99@comcast.com> Wrote in message:
> RichD wrote:
>> Presumably, most here are familiar with the concept of undecidability.
>>
>> My question is simple, though perhaps not the answer: Godel published
>> his results first, hence does Turing's non-computability theorem
>> (the halting problem), follow as a corollary?  What is the relationship
>> between these seemingly parallel theorems?
>>
> 
> I'm pretty sure Turing used Godel as part of his design of The Halting 
> Problem. It could effectively be considered a restatement of it.
> 
> There's little parallel about them; they're statements of the same basic 
> problem. At some level, they're quite different, at
> another they are exactly the same.
> 

You can derive thr incompleteness theorem _from_ the halting
 problem, if you make the (unjustified?) assumption that Peano
 arithmetic is consistent:

http://math.stackexchange.com/questions/53321/prove-g&#4294967295;dels-incompl
eteness-theorem-using-halting-problem
-- 


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

"RichD" <r_delaney2001@yahoo.com> wrote in message 
news:07e2f776-7bcf-4783-bd0e-f014e4434dc0@googlegroups.com...
> Presumably, most here are familiar with the concept of undecidability.
>
> My question is simple, though perhaps not the answer: Godel published
> his results first, hence does Turing's non-computability theorem
> (the halting problem), follow as a corollary?  What is the relationship
> between these seemingly parallel theorems?

One thing that has always concerned me about the Halting idea is that
we as humans can decide that something is undecidable but our brains do not
have to halt!