Re: A modern view of the halting problem


Herbert Kleebauer wrote:

You forgot an essential fact: a program running on a computer
with unlimited resources.

Uh, you're missing an essential fact. The Turing machine has unbounded
resources so that it can handle *any* algorithm out there. However, a
particular algorithm *must* use finite resources because you cannot
access an infinite amount of memory in a finite amount of time (you
*do* know the definition of an algorithm, right).


So the halting problem has nothing to
do with existing computers: there never was and never will be
a computer with an infinite amount of memory and for any program
running on a system with a finite amount of resources the halting
problem is trivial to solve.

Ah, yes. The ignorant speak. You might try studying some theoretical
computer science some time. Try Aho & Ullman, for example. A little
education would help prevent you from making such a fool of yourself in
public forums.



Randy know this and he also know that HLA isn't an assembler (or
more precise: the HLA system (hla.exe + backend assembler) isn't
an assembler and the HLA language isn't an assembly language).

Randy knows that the undecideability problem still applies to bounded
resource machines. More importantly, you cannot write a program that
runs on a finite-resource machine (bounded memory, and program steps)
that determines if another program always halts and produces a correct
answer for all input values. You and Chuck and anyone else for that
matter can argue until you're blue in the face, but that doesn't change
the facts. Unless you can disprove Church's hypothesis (that all
computable functions can be computed on a Turing machine), I'm afraid
you're barking up the wrong tree trying to claim that undecideability
doesn't apply on real-world machines.

And, just for the record, "Randy" knows that the HLA language is an
assembly language, and that HLA v1.x is a compiler for that language,
hence HLA v1.x is an assembler. The fact that you don't understand
some of the most basic concepts of computer science (such as
undecideability) that are related to formal languages certain
demonstrates that you're not in a good position to define terms in
computer science.

Cheers,
Randy Hyde

.

Relevant Pages

  • Re: HLA StdLib2 criticism
    ... HLC.EXE with an already existing C compiler and calls it HLC system. ... Suppose someone creates a new language and calls it "High Level ... Assembler" (HLA). ...
    (alt.lang.asm)
  • Re: What is an assembly language?
    ... HLA is an assembler. ... So what is this essential ability of an assembly language that is ... > that Randy-HLA isn't an x86 assembler. ...
    (alt.lang.asm)
  • Re: HLA StdLib2 criticism
    ... Assembler" (HLA). ... Can that person call this the "FASM language?" ... but also of course not he can call it an assembler ... Therefore HLC.EXE can't be called a compiler. ...
    (alt.lang.asm)
  • Re: HLA v2.x and / or LASM suggestion: Win32 Resources
    ... >> Beth, now it's obvious, you spent to much time with HLA. ... >> an assembler and therefore also an exe file with an included ... "RC" tool effectively means that you can't really put resources ... MASM because it won't do "flat binary" (when you say "any true Low ...
    (alt.lang.asm)
  • Re: What is an Assembler
    ... >> converts a HLA source to an executable. ... > knows the first thing about formal language design. ... convert an assembler source file to an executable (comparable ... it is a full compiler in every sense of the word. ...
    (alt.lang.asm)