Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #159301

Re: A small, slightly meta-, question

Show all headers | View raw

Manfred <noname@add.invalid> writes:

> On 3/11/2021 11:48 AM, Ben Bacarisse wrote:
>> John Forkosh <forkosh@panix.com> writes:
>>
>>> David Brown <david.brown@hesbynett.no> wrote:
>>>> On 10/03/2021 09:18, Mark Bluemel wrote:
>>>>> Is there any value in trying to understand Pete Olcott's posts?
>>>>
>>>> No. He is wrong. It's not difficult to prove that the halting problem
>>>> cannot be solved, [...]
>>>
>>> And since this is comp.lang.c, here's a little C program to prove it
>>> by contradiction (though it might equally as well be Fortran, etc).
>>>     Suppose you claim to have a function  int ishalts(char *filename)
>>> that reads a C program from filename and returns 1=the program in
>>> filename eventually halts, 0=it never halts, and -1=filename doesn't
>>> contain a valid C program (just so ishalts() is a total function
>>> from all_possible_strings-->{1,0,-1} rather than a partial function).
>
> [...]
>
>>
>>      /* save this program in file doIhalt.c */
>>      int main(void)
>>      {
>>         int ishalts(char *);
>>         while (ishalts("doIhalt.c") == 1) continue;
>>      }
>>
>> again, just to remove as much extraneous detail as possible.
>>
>>> So the program never halts if ishalts() claims that it eventually halts,
>>> and it immediately halts if ishalts() claims it never halts.
>>> Thus no such function ishalts() can exist with the claimed functionality.
>>> (I saw this example somewhere, but don't recall where.)
>>
>> I think I have as well.  The trouble is that using the file name to "tie
>> the knot" is really a cheat.  Not a cheat in a bad way (the argument is
>> sound and the conclusion is correct) but a student might well wonder if
>> halting for C programs is due to the fact that programs can be put into
>> named files, and other models, that don't have named files, would not be
>> subject to the same argument.
>
> Interesting objection. However, for an "ishalts()" function to exist a
> necessary condition is that a program can be addressed by some
> identifier. Then the same logic applies by making use of such
> identifier, be it named file or anything else.

Only if you stretch the meaning of the term "identifier".  In the
classical presentation, some direct encoding of the computation is
"passed".  For Turing machines, there is not way to refer a computation
using an identifier.  Instead a number is used that encodes (à la Gödel)
the state transition function of the subject TM.

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

A small, slightly meta-, question Mark Bluemel <mark.bluemel@gmail.com> - 2021-03-10 00:18 -0800
  Re: A small, slightly meta-, question Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-03-10 00:20 -0800
    Re: A small, slightly meta-, question Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-03-11 21:24 +0000
      Re: A small, slightly meta-, question om@iki.fi (Otto J. Makela) - 2021-03-15 14:40 +0200
  Re: A small, slightly meta-, question "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 00:30 -0800
  Re: A small, slightly meta-, question David Brown <david.brown@hesbynett.no> - 2021-03-10 10:04 +0100
    Re: A small, slightly meta-, question "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 20:40 -0800
    Re: A small, slightly meta-, question John Forkosh <forkosh@panix.com> - 2021-03-11 06:42 +0000
      Re: A small, slightly meta-, question Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-11 10:48 +0000
        Re: A small, slightly meta-, question Manfred <noname@add.invalid> - 2021-03-11 16:04 +0100
          Re: A small, slightly meta-, question Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-11 21:57 +0000
        Re: A small, slightly meta-, question John Forkosh <forkosh@panix.com> - 2021-03-12 06:29 +0000
  Re: A small, slightly meta-, question Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-03-10 05:51 -0800
    Re: A small, slightly meta-, question David Brown <david.brown@hesbynett.no> - 2021-03-10 16:03 +0100
  Re: A small, slightly meta-, question Bonita Montero <Bonita.Montero@gmail.com> - 2021-03-10 15:50 +0100
    Re: A small, slightly meta-, question Anton Shepelev <anton.txt@g{oogle}mail.com> - 2021-03-10 17:53 +0300
      Re: A small, slightly meta-, question Dolores Filandro <dolfiland8@gmail.com> - 2021-03-13 18:49 -0800
    Re: A small, slightly meta-, question "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-10 20:41 -0800
  Re: A small, slightly meta-, question Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-03-10 08:54 -0700
  Re: A small, slightly meta-, question "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-03-14 19:33 -0700

csiph-web