PEREIRA@SRI-AI.ARPA@sri-unix.UUCP (10/07/83)
This discussion assumes that "human minds" are at least equivalent to Universal Turing Machines. If they are restricted to computing smaller classes of recursive functions, the question dissolves. Sequential computers are idealized as having infinite memory because that makes it easier to study mathematically asymptotic behavior. Of course, we all know that a more accurate idealization of sequential computers is the finite automaton (for which there is no halting problem, of course!). The discussion on this issue seemed to presuppose that "minds" are the same kind of object as existing (finite!) computing devices. Accepting this presupposition for a moment (I am agnostic on the matter), the above argument applies and the discussion is shown to be vacuous. Thus fall undecidability arguments in psychology and linguistics... Fernando Pereira PS. Any silliness about unlimited amounts of external memory will be profitably avoided.
aaw@pyuxss.UUCP (11/04/83)
A point missing in this discussion is that the halting problem is equivalent to the question: Can a method be formulated to attempt to solve ANY problem which can determine if it is not getting closer to the solution so the meta-halters (not the clothing) can't be more than disguised time limits etc. for the general problem, since they CAN NOT MAKE INFERENCES ABOUT THE PROCESS they are to halt Aaron Werman pyuxi!pyuxss!aaw
warbob.rice%Rand-Relay@sri-unix.UUCP (11/05/83)
From: Bob.Warfield <warbob.rice@Rand-Relay>
It turns out that any computer program running on a real piece of hardware
may be simulated by a deterministic finite automaton, since it only has a
finite (but very large) number of possible states. This is usually not a
productive observation to make, but it does present one solution to the
halting problem for real (i.e. finite) computing hardware. Simulate the
program in question as a DFA and look for loops. From this, one should
be able to tell what input to the DFA would produce an infinite loop,
and recognition of that input could be done by a smaller DFA (the old
one sans loops) that gets incorporated into the learning program. It
would run the DFA in parallel (or 1 step ahead?) and take action if a
dangerous situation appeared.
Bob Warfield
warbob@ricejsol@bbncca.ARPA (Jon Solomon) (12/02/83)
Can a method be formulated for deciding whether or not your are on the right
track? Yes. It's call interaction. Ask someone you feel you can trust about
whether or not you are getting anywhere, and to offer any advice to help you
get where you want to go.
Students do it all the time, they come to their teachers and ask them to
help them. Looping programs could decide that they have looped for as long
as they care to and reality check them. An algorithm to do this is available
if anyone wants it (read that to mean I will produce one).
--
[--JSol--]
JSol@Usc-Eclc/JSol@Bbncca (Arpa)
JSol@Usc-Eclb/JSol@Bnl (Milnet)
{decvax, wjh12, linus}!bbncca!jsol