novaBBS - comp.lang.c - Halting problem and self-reference (liar paradox)

Halting problem and self-reference (liar paradox)

<afff29e6-906b-4218-9817-82f85b82e932n@googlegroups.com>

https://www.novabbs.com/devel/article-flat.php?id=17510&group=comp.lang.c#17510

X-Received: by 2002:ac8:665a:: with SMTP id j26mr8416767qtp.254.1626426053294; Fri, 16 Jul 2021 02:00:53 -0700 (PDT)
X-Received: by 2002:a37:5d5:: with SMTP id 204mr8754644qkf.17.1626426053028; Fri, 16 Jul 2021 02:00:53 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c
Date: Fri, 16 Jul 2021 02:00:52 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=58.115.187.102; posting-account=QJ9iEwoAAACyjkKjQAWQOwSEULNvZZkc
NNTP-Posting-Host: 58.115.187.102
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <afff29e6-906b-4218-9817-82f85b82e932n@googlegroups.com>
Subject: Halting problem and self-reference (liar paradox)
From: wyni...@gmail.com (wij)
Injection-Date: Fri, 16 Jul 2021 09:00:53 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 23

by: wij - Fri, 16 Jul 2021 09:00 UTC

Halting problem H is a decision PROBLEM (not a real program yet). If one tries
to write such a program:

// [Syn] Decide whether the function %f, given the argument %a, will halt or not,
//
// [Ret] true: f(a) will halt
// false: otherwise
//
// Note: %f is ANY program of the machine
//
bool H(Func f, Arg a);

Quick answer: By GUA https://groups.google.com/g/comp.theory/c/7dn3oEmo4Is
,HP is undecidable, i.e. no such correct H can exist.
See Also: https://www.geeksforgeeks.org/halting-problem-in-theory-of-computation/

There is no self-reference issue in such kind of problems governed by GUA.
Liar paradox is a different problem, any rebuttal just need to practically
write a real program (C, assembly, or TM) to demonstrate to see why, not just empty talk.

------
"C extremist" needs only to respond with a C program that compute H or
liar paradox. This is also an elementary problem to test whether you are
qualified to exist as a C-programmer or not.

Kirk to Enterprise -- beam down yeoman Rand and a six-pack.

devel / comp.lang.c / Halting problem and self-reference (liar paradox)

Subject	Author
Halting problem and self-reference (liar paradox)	wij