Re: The Halting Problem is _not_ solvable on real com

Article View: comp.lang.misc

Article #3812

#3812

From: Raul Rockwell
Date: Sat, 11 May 1991 01:52

17 lines
1193 bytes

Kenneth Walker:
   Is there any hope (in a theoretical sense) of a finite state
   machine computing interesting properties of an arbitrary finite
   state machine of its own size?

I don't think this is an interesting question.  :-)

An interesting question would be:  what properties should a
computation device have such that most practical programs can be
determined to halt.

This is related to proving a program correct.

I should note that functional languages seem to be rather promising
in this regard.

Raul Rockwell

Technical Details

Message-ID: <ROCKWELL.91May10205204@socrates.umd.edu>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell

References: <2990@optima.cs.arizona.edu> <1991May10.155454.2239@maths.nott.ac.uk> <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell
From: rockwell@socrates.umd.edu (Raul Rockwell)
Newsgroups: comp.lang.misc
Subject: Re: The Halting Problem is _not_ solvable on real com
Message-ID: <ROCKWELL.91May10205204@socrates.umd.edu>
Date: 11 May 91 01:52:04 GMT
References: <2990@optima.cs.arizona.edu> <1991May10.155454.2239@maths.nott.ac.uk>
 <3125@cirrusl.UUCP> <3069@optima.cs.arizona.edu>
Sender: rockwell@socrates.umd.edu (Raul Rockwell)
Organization: Traveller
Lines: 17
In-Reply-To: kwalker@cs.arizona.edu's message of 10 May 91 22: 56:01 GMT

Reply to Parent Message