From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public From: jmartin@kaiwan009.kaiwan.com (Jay M Martin) Subject: Re: What good is halting prob? Date: 1995/04/18 Message-ID: <3n27g6$4qr@kaiwan009.kaiwan.com>#1/1 X-Deja-AN: 101107944 references: <3kaksj$iur@isnews.calpoly.edu> <3mve9b$gaj@news.cais.com> organization: KAIWAN Internet (310-527-4279,818-756-0180,909-785-9712,714-638-4133,805-294-9338) newsgroups: comp.lang.ada,comp.edu Date: 1995-04-18T00:00:00+00:00 List-Id: In <3mve9b$gaj@news.cais.com> crawford@cais2.cais.com (Randolph Crawford) writes: >As a final point, one of the reasons why this stuff is often presented >as part of a CS theory course on formal automata is the simplicity of >showing undecidability and the halting problem using Turing machines. >Once the student understands that this undecidability holds for Turing >machines, it becomes clear that it holds for all kinds of languages/ >automata/machines as well, like BASIC and C. >It also happens that this class of undecidable programs is called >Universal Turing Machines -- which is another reason to introduce the >halting problem and undecidability at the same time as Turing machines. I think Turing machines are pretty silly and see an idealized register or random access machine as a much better way to present this stuff. To me its just one of many "Dumb ideas of Computer Science" that are sort of anarchisms but still survive. I put lambda calculus and algol style nesting in this category too. Jay