Re: Can returning a value change the value itself (in the Halting Problem)

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 08/18/04 

Date: Wed, 18 Aug 2004 18:08:08 +0200

Peter Olcott wrote:
> Many of the attempts at refuting my refutation of the Halting Problem
> implicitly assumed that the answer to this question is no.

Assumed or deduced, with any reasonable clarification of the
title question, "no" is a more reasonable answer than "yes".

> They try to
> prove that my refutation is wrong by making this false assumption.
> Instead of keeping this false assumption hidden under the cover of
> rhetoric, let's analyze it explicitly.
>
> The goal of this thread is to analyze each and every step exactly
> one step at a time until this question has final resolution that most
> everyone can agree to.

I think you've brought out many implicit assumptions of the
ideas surrounding the halting problem. Also you've voiced
many questions that commonly are raised.

Here's what I think are the difficulties (and the sole
content to this message):

- proof by contradiction (that is the rhetorical strategy of
assuming something, showing it leads to bad things (like
0=1)).

- dealing with quantifiers: for all, there exists and
negation.

- dealing with abstraction: not just one example of a bad TM
but a representative for all possible halting TMs.

- the informal construction of the diagonalized TM (or
mostly that it is easily formalized)

- the apparent self reference, and the inference of
contradiction.

- dealing with use-mention, Universal TMs, encodings,
simulation.

I think the first and the last are the most troublesome,
that is counterintuitive, but also the most likely to be
discussed well in any textbook.

I think if we did this step by step, we'd be repeating
ourselves, from what we've done repeating ourselves many
times over..already...before... again. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages