home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / prolog / 1620 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  2.0 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!rsg1.er.usgs.gov!fmsrl7!lynx!nmsu.edu!opus!ted
  2. From: ted@nmsu.edu (Ted Dunning)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: Help on problem needed!
  5. Message-ID: <TED.92Aug28211631@pylos.nmsu.edu>
  6. Date: 29 Aug 92 04:16:31 GMT
  7. References: <meskes.713709771@ulysses> <1992Aug25.074623.25450@greco-prog.fr>
  8.     <14219@goanna.cs.rmit.oz.au> <meskes.714916931@ulysses>
  9. Sender: usenet@nmsu.edu
  10. Reply-To: ted@nmsu.edu
  11. Organization: Computing Research Lab
  12. Lines: 35
  13. In-Reply-To: meskes@ulysses.informatik.rwth-aachen.de's message of 27 Aug 92 12:02:11 GMT
  14.  
  15.  
  16. In article <meskes.714916931@ulysses>
  17. meskes@ulysses.informatik.rwth-aachen.de (Michael Meskes) writes:
  18.  
  19.    All the answers are quite interesting but the don't solve the
  20.    problem.  As far as I know Prolog is turing-complete and the proofs
  21.    I know don't use the Cut. So why isn't it possible to solve this
  22.    problem im Prolog?
  23.  
  24. rok put his thumb on the answer... you can easily interpret languages
  25. which implement things like if/then/else in pure prolog even if you
  26. can't implement if/then/else directly.  in particular, the code for a
  27. turing machine interpreter is only a few lines.  this proves turing
  28. equivalence, and means that if you really wanted to, you could write
  29. an interpreter for prolog _with_ a cut to run on this turing machine.
  30. this wouldn't count as a correct answer on most exams (or homeworks!).
  31.  
  32. Just for example, here is just such a simulator (the turing machine
  33. program is encoded in the step predicate):
  34.  
  35. turing(Tape, State, FinalTape, FinalState) :-
  36.     step(State, Visible, NewState, NewCell, Direction),
  37.     change_tape(NewCell, Tape, Direction, NewTape),
  38.     turing(NewTape, NewState, FinalTape, FinalState).
  39.  
  40. turing(Tape, done, Tape, done).
  41.  
  42. change_tape(New, tape(_, [L|Left], Right), left, tape(L, Left, [New|Right])).
  43. change_tape(New, tape(_, Left, [R|Right]), right, tape(R, [New|Left], Right)).
  44.     
  45.     
  46. --
  47.  
  48. There ain't nothin' in this world that's worth being a snot over.
  49.     Larry Wall
  50.