Ideas
Steven Frew
Just a message to generate discussion ... it's been a while since I last
used Inform, so some of what I'm about to say might be embarrassingly
out-of-date. Still, here goes:
A few years ago, upon discovering that IF was still flourishing, I tried to
write my own piece of IF (called "Derwents Uncertain Future") for the IF
contest.
It was a bit ambitious: there were about five major puzzles, one of them
involving a robot who you issued commands to by writing them on a piece of
card and inserting them into a slot in it's chest. I was a bit tired of
NPC's who acted more-or-less like mobile scenery, only reacting to a handful
of actions, so the robot was my response to that. It would then go off and
perform the commands you wrote, one per turn, unquestioningly. It was, to
all extents and purposes, a remote control player.
Anyway, this aspect of the game required a LOT of work, mainly modifying the
inform parser, and I reached several conclusions before abandoning the game.
The default method of treating the player as "you" and non-players as
less-sophisticated beings was inadequate. Revamping the libraries to make
the robot do whatever was asked made me think how much it applied to
characters in general. There is a trend in IF for NPC's to be as
uncooperative as possible:
> JULIE, PASS THE MUSTARD
Your wife ignores you, and continues eating.
... when the real world is not like that. Making characters more dynamic is
often seen as too much hard work. Granted, giving non-players the
intelligence to behave appropriately in all circumstances is a bit
ambitious:
> ROSINA, STAB YOURSELF WITH PENCIL
Rosina snorts. "No thanks! That would incur painful death!"
... but at the very least all characters should be able to act as "faithful
servants" by default, with the user limiting them. However, instead of
limiting a character to a strict user-defined set of actions, characters
could be given "cooperability" properties, determining how much they trust
the player. This could change throughout the game. Actions would have
related properties that could be played off against cooperability, so
someone who "sort of" trusts you won't assassinate a character on your
request, but they probably will fetch you a pen. The output from actions
would be dynamic enough to recognise what "person" the writing should be in,
so no specialised text would be necessary.
Also, actions should be more atomic. Imagine a room where there is a ruby on
a podium:
> TAKE RUBY
You reach for the ruby, but invisible high-density lasers shred your hand
into a fleshy mist. You die through loss of blood.
Simple enough to do. Trap the take command, and kill the player. But what
about:
> EAT RUBY
> KISS RUBY
> PUNCH RUBY
The same test would be needed in every function that requires physical
contact with the ruby. A better method would be to make any such
physical-contact function call a succession of sub-actions in order, like
MoveTowards, ReachFor, Touch, Hold, then finally Take (or, in the other
cases, Eat, or Kiss). So if touching an object causes a response, you would
code such a response in the Touch action, and all other functions like Take,
Eat, Kiss, etc would trigger that response through the Touch action, AND
NOWHERE ELSE. Of course, unless an action in the chain generated an
unexpected result, all output from actions other than the last would be
hidden.
What I've described would only touch on the whole scope of the thing. I'm
looking towards an IF "engine" where everything is handled as default, where
there is a reasonably good simulation of basic laws of a real world going
on, where objects have an enormous number default properties that are very
closely tied to the physical world model. I realise that I'm beginning to
sound like a scientist more than a writer, but personally, I reckon IF would
benefit from this more generic and atomic approach to actions, and when
authors are freed from having to write code to test whether a character can
reach an object on a high shelf, or code to make sure the player can't carry
anything else while carrying the 1950's-style fridge,and concentrate more on
story, it can only be good.
I -did- get the robot puzzle working, in case anyone was wondering ... :)
Looking forward to a good bit of debate,
Froo
Gareth Rees
> actions should be more atomic
More atomic than what?
The history of world-modelling in adventure games is one of extending
world models and finding new sets of atomic actions. This is a result
of pressure from games which require complicated exceptions.
For example, "take" was originally an atomic action: if you can see it
and its portable you can take it. In "Advent"-like games there's no
need for anything more complex -- a game might have one or two
exceptional situations (say, a bird that can be put into a cage), but
these can be handled satisfactorily with a bit of coding (say, when you
take the bird while carrying the cage you get rid of the bird and cage
objects and replace them with a bird-in-cage object).
Then there were games like "Zork" that wanted to have containers and
vehicles. This is a pain to implement in the "take"-is-atomic world of
"Advent", so "take" was extended to understand the containment model.
Then there were games that wanted to have objects that were visible but
not touchable -- transparent containers, rooms separated by glass
windows, high shelves, trapdoors in the ceiling. This is possible to
implement in the "Zork"-like world model: you make sure to trap actions
like "take" that involve touching things out of reach. But it's a pain.
It's neater to extend "take" so that "take thing" becomes "touch thing
then take thing" -- then you only have to trap "touch" actions. (This
is roughly what Inform does at the moment. TADS' "WorldClass" is
similar.)
There's no end to the increased richness that you might demand of a
world model. In the Inform system the programmer has to provide rules
saying what is touchable from where -- you could imagine a system which
modelled roughly the position and size of objects and could work out for
itself what was touchable from where. Then you could imagine doing
static and dynamic simulation of mass, inertia, friction...
But increased richness of world model doesn't come cost-free. In a
richer system, the game developer has to do a lot more work to specify
the physical characteristics of objects. And there is a lot more
potential for bugs -- the more states the world has the smaller the
fraction that testing can cover.
--
Gareth Rees
Adam J. Thornton
Steven Frew <steve...@cadspace.com> wrote:
>What I've described would only touch on the whole scope of the thing. I'm
>looking towards an IF "engine" where everything is handled as default, where
>there is a reasonably good simulation of basic laws of a real world going
>on, where objects have an enormous number default properties that are very
>closely tied to the physical world model. I realise that I'm beginning to
>sound like a scientist more than a writer, but personally, I reckon IF would
>benefit from this more generic and atomic approach to actions, and when
>authors are freed from having to write code to test whether a character can
>reach an object on a high shelf, or code to make sure the player can't carry
>anything else while carrying the 1950's-style fridge,and concentrate more on
>story, it can only be good.
That'd basically be an RPG.
Really.
If you want to do physical-world simulation, you're closer to the RPG genre
than to text adventures. Not to say it wouldn't be IF, and of course you
could do it with a text UI. However, the best place for you to start
investigating this would be in RPG development and research.
Adam
--
ad...@princeton.edu
"My eyes say their prayers to her / Sailors ring her bell / Like a moth
mistakes a light bulb / For the moon and goes to hell." -- Tom Waits
Kevin Forchione
news:si1zbxf...@cre.canon.co.uk...
> Then there were games that wanted to have objects that were visible but
> not touchable -- transparent containers, rooms separated by glass
> windows, high shelves, trapdoors in the ceiling. This is possible to
> implement in the "Zork"-like world model: you make sure to trap actions
> like "take" that involve touching things out of reach. But it's a pain.
> It's neater to extend "take" so that "take thing" becomes "touch thing
> then take thing" -- then you only have to trap "touch" actions. (This
> is roughly what Inform does at the moment. TADS' "WorldClass" is
> similar.)
"visibility" and "reachability" rules which are based on attributes of an
object, but in general work from a "bubble-up/filter-down" approach, which
means that a scope ceiling is established and then accessibility is
determined by working down through contents.
In TADS the normal "ceiling" is the room object that the actor is in. But
WorldClass gets around this by containing all such objects within a "top",
and so the ceiling becomes more inclusive and "sense" actions have wider
scope. It then becomes a matter of "connections" which define the boundaries
of scope.
Where do you see it going from here? I agree with your comments about
trade-offs. The other problem, of course is that as the world model becomes
increasingly more complex, the broader the web of rules that bind object
behaviours becomes. As a small example, realistically, animate objects
require food, water, and generally sleep. It would become quite annoying if
the NPC you're dealing with suddenly got up and left to go in search of a
bed. Or if Sherlock were to decide to spend the £5 you gave him to buy a
meal.
--Kevin
Gene Wirchenko
>In article <7rtibq$o5l$1...@flex.pipex.net>,
>Steven Frew <steve...@cadspace.com> wrote:
>>What I've described would only touch on the whole scope of the thing. I'm
>>looking towards an IF "engine" where everything is handled as default, where
>>there is a reasonably good simulation of basic laws of a real world going
>>on, where objects have an enormous number default properties that are very
>>closely tied to the physical world model. I realise that I'm beginning to
>>sound like a scientist more than a writer, but personally, I reckon IF would
>>benefit from this more generic and atomic approach to actions, and when
>>authors are freed from having to write code to test whether a character can
>>reach an object on a high shelf, or code to make sure the player can't carry
>>anything else while carrying the 1950's-style fridge,and concentrate more on
>>story, it can only be good.
>
>That'd basically be an RPG.
>
>Really.
>
>If you want to do physical-world simulation, you're closer to the RPG genre
>than to text adventures. Not to say it wouldn't be IF, and of course you
>could do it with a text UI. However, the best place for you to start
>investigating this would be in RPG development and research.
OTOH, encumbrance rules are a pain in AD&D (and probably nearly
any other system as well) and are often ignored (or close to it).
There was a cartoon several years ago in "Dragon" which showed one
adventurer with a huge pack (10' high or so and other dimensions as
ridiculous) stuffed to overflowing and a second adventurer asking
something like "So if you just ignore encumbrance, then it doesn't
exist?"
It sure would be easier with the computer tracking it.
Sincerely,
Gene Wirchenko
Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
BrenBarn
>looking towards an IF "engine" where everything is handled as default, where
>there is a reasonably good simulation of basic laws of a real world going
>on, where objects have an enormous number default properties that are very
>closely tied to the physical world model.
included in a new IF engine. These ideas sound very interesting, and
undoubtedly merit discussion. I, for one, would love to start actually talking
about the system of verbs, nouns, properties, etc. that might be used in such
an engine.
From,
Brendan B. B. (Bren...@aol.com)
(Name in header has spam-blocker, use the address above instead.)
"Do not follow where the path may lead;
go, instead, where there is no path, and leave a trail."
--Author Unknown
David Given
"Steven Frew" <steve...@cadspace.com> writes:
[...]
> Also, actions should be more atomic. Imagine a room where there is a ruby on
> a podium:
>
>> TAKE RUBY
> You reach for the ruby, but invisible high-density lasers shred your hand
> into a fleshy mist. You die through loss of blood.
>
> Simple enough to do. Trap the take command, and kill the player. But what
> about:
>
>> EAT RUBY
>> KISS RUBY
>> PUNCH RUBY
If often thought that an owner-based system would work quite well. All
actions boil down to a sequence of manipulations. Some types of
manipulations require ownership of the object, some don't.
So:
TAKE RUBY
becomes:
transfer RUBY from PODIUM to PLAYER
and:
EAT RUBY
...becomes:
transfer RUBY from PODIUM to PLAYER
PLAYER consumes RUBY
So, the podium would trap all operations to an object in its ownership and
abort the sequence at the `transfer' stage.
So far, this isn't too different from the normal system. So, how about:
THROW ROCK AT RUBY
...?
transfer ROCK to AIR
ROCK is-thrown-at RUBY
ROCK strikes RUBY
transfer ROCK from AIR to GROUND
transfer RUBY from PODIUM to AIR
transfer RUBY from AIR to GROUND
(I'm assuming here that when you throw a rock at something it pushes it,
and the ruby, when struck, falls off the podium.)
So, the podium traps the rock pushing the ruby; but since the rock's not
animate, it's not killable, so the podium has to let the action through.
You'd have to specify the various domains that touch each other. So, air
touches everything; but the fusebox doesn't touch the podium. So for
something inside the fusebox to manipulate something on the podium it must
go through an intermediary.
...imagine replacing the podium with a cabinet. Now, the ruby is no longer
in contact with the air, so the above example doesn't work.
transfer ROCK to AIR
ROCK is-thrown-at RUBY
(RUBY is inside CABINET)
ROCK is-thrown-at CABINET
ROCK strikes CABINET
transfer ROCK from AIR to GROUND
CABINET shatters
CABINET is-replaced-by BROKEN-CABINET
This requires lots of fiddly scoping, though. At the beginning, the
following applies:
AIR is-supported-by GROUND
PLAYER is-supported-by GROUND
ROCK is-contained-by PLAYER
CABINET is-supported-by GROUND
PODIUM is-contained-by CABINET
RUBY is-supported-by PODIUM
...and at the end:
AIR is-supported-by GROUND
PLAYER is-supported-by GROUND
ROCK is-supported-by GROUND
BROKEN-CABINET is-supported-by GROUND
PODIUM is-supported-by GROUND
RUBY is-supported-by PODIUM
Hmm. This looks tailor-made for Prolog.
Is this feasible? Useful? Desirable? Or have I just reinvented the wheel,
and square at that?
--
+- David Given ---------------McQ-+
| Work: d...@tao-group.com | Resist the resistance!
| Play: dgi...@iname.com |
+- http://wired.st-and.ac.uk/~dg -+
Albert
<7rtibq$o5l$1...@flex.pipex.net>:
>Also, actions should be more atomic. Imagine a room where there is a ruby on
>a podium:
>
>> TAKE RUBY
>You reach for the ruby, but invisible high-density lasers shred your hand
>into a fleshy mist. You die through loss of blood.
>
>Simple enough to do. Trap the take command, and kill the player. But what
>about:
>
>> EAT RUBY
>> KISS RUBY
>> PUNCH RUBY
>
>The same test would be needed in every function that requires physical
>contact with the ruby. A better method would be to make any such
>physical-contact function call a succession of sub-actions in order, like
>MoveTowards, ReachFor, Touch, Hold, then finally Take (or, in the other
>cases, Eat, or Kiss). So if touching an object causes a response, you would
>code such a response in the Touch action, and all other functions like Take,
>Eat, Kiss, etc would trigger that response through the Touch action, AND
>NOWHERE ELSE. Of course, unless an action in the chain generated an
>unexpected result, all output from actions other than the last would be
>hidden.
>
>What I've described would only touch on the whole scope of the thing. I'm
>looking towards an IF "engine" where everything is handled as default, where
>there is a reasonably good simulation of basic laws of a real world going
>on, where objects have an enormous number default properties that are very
>closely tied to the physical world model. I realise that I'm beginning to
This leads to the question of whether realism truly adds to gameplay.
If we do add "enormous number of default properties", then where would we
stop? And simulating all of this under a text environment would be
difficult and I can only imagine that it would be easier with a 3D engine.
>Looking forward to a good bit of debate,
>Froo
--
Albert ICQ: 14617788
http://members.home.com/ajyi
"I don't know why I did it,
I don't know why I enjoyed it,
and I don't know why I'll do it again."
- Bart Simpson
Andrew Plotkin
> Also, actions should be more atomic. Imagine a room where there is a ruby on
> a podium:
>
>> TAKE RUBY
> You reach for the ruby, but invisible high-density lasers shred your hand
> into a fleshy mist. You die through loss of blood.
>
> Simple enough to do. Trap the take command, and kill the player. But what
> about:
>
>> EAT RUBY
>> KISS RUBY
>> PUNCH RUBY
>
> The same test would be needed in every function that requires physical
> contact with the ruby. A better method would be to make any such
> physical-contact function call a succession of sub-actions in order, like
> MoveTowards, ReachFor, Touch, Hold, then finally Take (or, in the other
> cases, Eat, or Kiss). So if touching an object causes a response, you would
> code such a response in the Touch action, and all other functions like Take,
> Eat, Kiss, etc would trigger that response through the Touch action, AND
> NOWHERE ELSE. Of course, unless an action in the chain generated an
> unexpected result, all output from actions other than the last would be
> hidden.
I once starting working on something like this. (No, never got anywhere.)
But I didn't think of it at all as "simulationist", nor as anything
related to your other proposal. It's a way of organizing *abstract*
actions. Not in a general way, but in a customizable way.
You could write a game that had different areas of rooms, for example, by
adding an additional layer of "within reach" range below the usual "in the
same room" range. With the appropriate default actions: "(walking over to
the bookcase)". Or, create a particular object where reaching for it
produces special consequences -- say, a jewel protected by a motion
detector.
You can't possibly write this as a general library infrastructure; every
game has different needs, and you'll always find an author who wants one
more level than you put in. You have to make something which is simple,
but extendable.
(There are whole games out there, unwritten, where smell and hearing have
as many levels of range-distinction as touch normally does. And, of
course, some games invent new senses.)
--Z
"And Aholibamah bare Jeush, and Jaalam, and Korah: these were the
borogoves..."
Andrew Plotkin
>>What I've described would only touch on the whole scope of the thing. I'm
>>looking towards an IF "engine" where everything is handled as default, where
>>there is a reasonably good simulation of basic laws of a real world going
>>on, where objects have an enormous number default properties that are very
>>closely tied to the physical world model.
> Coincidentally, there is an ongoing thread about what features should be
> included in a new IF engine.
So, what *do* you mean by "engine"?
BrenBarn
to post exactly how I was using the term "engine" on the "other thread" I
mentioned. As an added bonus, I defined how I was using a few other terms as
well. :-)
Daniel Barkalow
> The default method of treating the player as "you" and non-players as
> less-sophisticated beings was inadequate. Revamping the libraries to make
> the robot do whatever was asked made me think how much it applied to
> characters in general. There is a trend in IF for NPC's to be as
> uncooperative as possible:
>
> > JULIE, PASS THE MUSTARD
> Your wife ignores you, and continues eating.
At the very least, I'd like to see NPCs be able to use the library code
that the player uses to manipulate items. That is, so an NPC can "give
player flashlight" if she wants to without having to include the code for
giving stuff to people specially. Ditto for movement and such. There
doesn't have to be any intelligence in the system, just the availability
of the routines to the programmer.
This would alleviate a large portion of the difficulty of making NPCs:
they need lots of checks to make sure they won't follow commands that
they should not be able to. For each ability you give a character, you
have to limit it to what should be possible, using essentially the same
limits that the player has.
-Iabervon
*This .sig unintentionally changed*
Joe Mason
> On Fri, 17 Sep 1999, Steven Frew wrote:
>
> > The default method of treating the player as "you" and non-players as
> > less-sophisticated beings was inadequate. Revamping the libraries to make
> > the robot do whatever was asked made me think how much it applied to
> > characters in general. There is a trend in IF for NPC's to be as
> > uncooperative as possible:
> >
> > > JULIE, PASS THE MUSTARD
> > Your wife ignores you, and continues eating.
You know, I just got back from seeing The Sixth Sense. I guess everybody who's
seen the movie will know what I'm getting at here...
Joe
Christoffer Karlsson
> Hmm. This looks tailor-made for Prolog.
Yes, indeed it is. I wrote a small compiler for a specialized subset of
Prolog that generated Z-machine code (named Zolog of course...).
> Is this feasible? Useful? Desirable? Or have I just reinvented the wheel,
> and square at that?
For me there were two major problems; the Inform library has to be
rewritten to better accommodate this style of programming and one has to
be *very* careful when writing programs in order to make certain they
terminate (this made testing extremely difficult). (I also had problems
with the fact that Inform 6.12 reversed the meaning of RFALSE and RTRUE
which had me quite puzzled for a while!).
To summarize: it can be very convenient but does not really seem
feasible as it is difficult to make sure that actions will terminate.
--
Christoffer Karlsson
Macintosh Software Developer
Philip W. Darnowsky
: For me there were two major problems; the Inform library has to be
: rewritten to better accommodate this style of programming and one has to
: be *very* careful when writing programs in order to make certain they
: terminate (this made testing extremely difficult).
No problem; I've written a program in Inform that can check whether any
Inform program terminates in finite time.
"Inform: Turing Complete And So Much More."
--
---------------------------------------------------------------
Phil Darnowsky pdar...@spameggsbaconandspam.qis.net
Remove spam, eggs, bacon, spam, and dot to reply.
"I'd use 'Hitler-Ware' if it would get the job done."
--Terry Fry
David Glasser
> Christoffer Karlsson (c...@kagi.com) wrote:
>
> : For me there were two major problems; the Inform library has to be
> : rewritten to better accommodate this style of programming and one has to
> : be *very* careful when writing programs in order to make certain they
> : terminate (this made testing extremely difficult).
>
> No problem; I've written a program in Inform that can check whether any
> Inform program terminates in finite time.
>
> "Inform: Turing Complete And So Much More."
You're joking, right?
--
David Glasser | gla...@iname.com | http://www.davidglasser.net/
rec.arts.int-fiction FAQ: http://www.davidglasser.net/raiffaq/
'No, GLK is spelled "G L K". What is this Java you speak of?'
--Joe.Mason on that portable thing on rec.arts.int-fiction
Ok, ok, if you want to nitpick there does exist a program to do this
because the ZMachine format is finite, but it's probably impossible (and
I mean that literally) to construct it.
Christopher Nebel
gla...@iname.com (David Glasser) wrote:
>Philip W. Darnowsky <pdar...@qis.net> wrote:
>
>> Christoffer Karlsson (c...@kagi.com) wrote:
>>
>> : For me there were two major problems; the Inform library has to be
>> : rewritten to better accommodate this style of programming and one has to
>> : be *very* careful when writing programs in order to make certain they
>> : terminate (this made testing extremely difficult).
>>
>> No problem; I've written a program in Inform that can check whether any
>> Inform program terminates in finite time.
>>
>> "Inform: Turing Complete And So Much More."
>
>You're joking, right?
He's joking. It can't be done in Inform. RAIF-POOL, maybe, but not Inform.
>Ok, ok, if you want to nitpick there does exist a program to do this
>because the ZMachine format is finite, but it's probably impossible (and
>I mean that literally) to construct it.
Actually, there still doesn't, because the halting proof doesn't rely on
the notion of unbounded program length. There are perfectly finite (and
even quite small!) programs that can't be proven to halt or not.
You're correct in that you could, given enough time and memory, construct
a table of all possible Inform programs. Because Inform has a fixed upper
size, this is a finite set. You could then try to determine for each one
whether it eventually stops, runs forever, or has any literary merit.
However, your table would have gaps in it, because you wouldn't be able to
prove whether or not some of the programs halted.
--Christopher Nebel
P.S.: I'm pretty certain this is correct if the proving program must be
written in Inform, but it might be possible if it's written using
something else. The Incompleteness Theorem says that within any
self-consistent set of axioms, it's possible to write statements that
can't be proven true or false _within that same system_. It does not
preclude the possibility of inventing some other system that can prove
those previously unsolvable statements, though of course the new system
has its own unprovable statements as well. The tricky bit, of course, is
that all Turing-complete languages are essentially equivalent -- in order
to solve the halting problem, you'd need something better than
Turing-complete, and I don't know if that's even possible.
Peter Seebach
Christopher Nebel <c.n...@apple.com> wrote:
>P.S.: I'm pretty certain this is correct if the proving program must be
>written in Inform, but it might be possible if it's written using
>something else. The Incompleteness Theorem says that within any
>self-consistent set of axioms, it's possible to write statements that
>can't be proven true or false _within that same system_.
Any self-consistent set of axioms strong enough to model arithmetic. I
think that requires the capacity for bignums. :)
Anyway, I wouldn't worry about it; the halting problem is still Too Hard.
-s
--
Copyright 1999, All rights reserved. Peter Seebach / se...@plethora.net
C/Unix wizard, Pro-commerce radical, Spam fighter. Boycott Spamazon!
Will work for interesting hardware. http://www.plethora.net/~seebs/
Visit my new ISP <URL:http://www.plethora.net/> --- More Net, Less Spam!
Avrom Faderman
Peter Seebach wrote in message ...
[discussion of the solubility or not of the halting problem for inform]
Search Deja News for "halting problem" with forum=rec.arts.int-fiction.
This question was discussed at great length then.
Best,
Avrom
David Glasser
> >Ok, ok, if you want to nitpick there does exist a program to do this
> >because the ZMachine format is finite, but it's probably impossible (and
> >I mean that literally) to construct it.
>
> Actually, there still doesn't, because the halting proof doesn't rely on
> the notion of unbounded program length. There are perfectly finite (and
> even quite small!) programs that can't be proven to halt or not.
>
> You're correct in that you could, given enough time and memory, construct
> a table of all possible Inform programs. Because Inform has a fixed upper
> size, this is a finite set. You could then try to determine for each one
> whether it eventually stops, runs forever, or has any literary merit.
> However, your table would have gaps in it, because you wouldn't be able to
> prove whether or not some of the programs halted.
I'm mostly just parroting back what I picked up here on raif. My point
was that this program *exists*, but it may be impossible (is
impossible?) to *construct* this program and know that it is the "right"
program. (Well, this was Andrew Plotkin's point when I heard it.)
It's like in Borges' library of babel: one of those books is the table
of halting Inform programs, but we don't know which one.
--
David Glasser | gla...@iname.com | http://www.davidglasser.net/
rec.arts.int-fiction FAQ: http://www.davidglasser.net/raiffaq/
"Maybe Glulxification will cause people to start using Scheme for IF. Or
maybe not. Anyhow, I just like saying 'Glulxification'." -andyf on ifMUD
Peter Seebach
Avrom Faderman <fade...@pacbell.net> wrote:
>Search Deja News for "halting problem" with forum=rec.arts.int-fiction.
>This question was discussed at great length then.
Drat. I'm sure the search will find the article, but my search is taking
forever.
Maybe I shouldn't have asked it to find articles about searching for articles
about the halting problem.
Michael Naunton
>
> In article <1dyfu01.1f4...@usol-209-186-16-200.uscom.com>,
> gla...@iname.com (David Glasser) wrote:
>
> >Philip W. Darnowsky <pdar...@qis.net> wrote:
> >
> >> Christoffer Karlsson (c...@kagi.com) wrote:
> >>
> >> : For me there were two major problems; the Inform library has to be
> >> : rewritten to better accommodate this style of programming and one has to
> >> : be *very* careful when writing programs in order to make certain they
> >> : terminate (this made testing extremely difficult).
> >>
> >> No problem; I've written a program in Inform that can check whether any
> >> Inform program terminates in finite time.
> >>
> >> "Inform: Turing Complete And So Much More."
> >
> >You're joking, right?
>
> He's joking. It can't be done in Inform. RAIF-POOL, maybe, but not Inform.
>
> >because the ZMachine format is finite, but it's probably impossible (and
> >I mean that literally) to construct it.
>
> Actually, there still doesn't, because the halting proof doesn't rely on
> the notion of unbounded program length. There are perfectly finite (and
> even quite small!) programs that can't be proven to halt or not.
But, given that the ZMachine does not provide infinite data space, you
can,
in principle, test if any given program halts.
> You're correct in that you could, given enough time and memory, construct
> a table of all possible Inform programs. Because Inform has a fixed upper
> size, this is a finite set. You could then try to determine for each one
> whether it eventually stops, runs forever, or has any literary merit.
> However, your table would have gaps in it, because you wouldn't be able to
> prove whether or not some of the programs halted.
See above.
> --Christopher Nebel
>
> P.S.: I'm pretty certain this is correct if the proving program must be
> written in Inform, but it might be possible if it's written using
> something else. The Incompleteness Theorem says that within any
> self-consistent set of axioms, it's possible to write statements that
> can't be proven true or false _within that same system_. It does not
> preclude the possibility of inventing some other system that can prove
> those previously unsolvable statements, though of course the new system
> has its own unprovable statements as well. The tricky bit, of course, is
> that all Turing-complete languages are essentially equivalent -- in order
> to solve the halting problem, you'd need something better than
> Turing-complete, and I don't know if that's even possible.
True. For any program in Inform, we need a system with twice the total
usable space (plus a constant) to prove the halting of the inform
program.
regards,
Michael Naunton
cozmo
<intro snip>
> It was a bit ambitious: there were about five major puzzles, one of them
> involving a robot who you issued commands to by writing them on a piece of
> card and inserting them into a slot in it's chest. I was a bit tired of
<snip>
> The default method of treating the player as "you" and non-players as
> less-sophisticated beings was inadequate. Revamping the libraries to make
> the robot do whatever was asked made me think how much it applied to
> characters in general. There is a trend in IF for NPC's to be as
> uncooperative as possible:
>
> > JULIE, PASS THE MUSTARD
> Your wife ignores you, and continues eating.
Steven, I agree this is a rather difficult part of IF. The complexities
of an NPC require really good planning in story line or an IF engine
that is truly AI.
<snip>
> ... but at the very least all characters should be able to act as "faithful
> servants" by default, with the user limiting them. However, instead of
> limiting a character to a strict user-defined set of actions, characters
> could be given "cooperability" properties, determining how much they trust
> the player. This could change throughout the game. Actions would have
> related properties that could be played off against cooperability, so
> someone who "sort of" trusts you won't assassinate a character on your
> request, but they probably will fetch you a pen. The output from actions
> would be dynamic enough to recognise what "person" the writing should be in,
> so no specialised text would be necessary.
What you are describing is (IMHO) a little beyond our current AI
ability. It seems to me you are looking to give potential authors a
great big special effects department they don't really need. I hope I
don't go off topic here. I feel my insight might be helpful.
I am a professional Magician. My 'job' is to entertain people with the
art of illusion. My interest in computers and IF early in my life has
certainly contributed to my success. As a magician that specialises in
close-up magic I know for a fact that 'technical ability' is not equated
with 'entertainment value' in a medium. To use a cliche 'it's canvas'.
If you look at some of the best (imho) NPC's, they were not great
characters due to the simulation ability of the engine, but due to the
excellent writing on the artist's part.
i.e. Floyd from Planetfall. Floyd was a 'faithful servent', yet his
'character' came from some artistic and intelligent writing and story
telling on the authors part. One of the cleverest uses of an NPC (which
I have just recently discovered) is the 'stranger' in edifice. Using a
limited ability to communicate, the stranger and the NPC have a
conversation. Lucian Smith made a character who was usefull and far
from a 'faithful servent'.
I must admit I have wished for inform to be able to take source code
like:
npc.go_s; npc.get(rock)
Yet the results will allways depend on the person writing the code. A
'programmer' free NPC is (imho) an oxymoron.
In ending...
"Any sufficiently advanced technology is indisguishable from magic."
"Any sufficiently advanced magic is probably a rigged demo."
Cozmo the Magician
www.superior.net/~cozmo
Kevin Forchione
simulation and a work of fiction. As I have stated before, memorable stories
are not the result of mirroring reality, but of a deft presentation of the
most dramatic details.
--Kevin
Gareth Rees
> No problem; I've written a program in Inform that can check whether
> any Inform program terminates in finite time.
It *is* possible to determine in finite time whether or not an Inform
program that doesn't take input terminates (though not with another
Inform program, obviously).
This is because Inform programs deal with a finite amount of data.
There's no mechanism for dynamic allocation of memory, so each Inform
program has a finite number of possible states (say, N). You can
determine if the program halts by simulating it for N steps -- after
which if it hasn't halted then it must have entered a loop and therefore
will never halt.
The problem of determining if an Inform program halts is therefore
PSPACE-complete. (It's obviously in PSPACE, and polynomial
transformation from, say, IN-PLACE ACCEPTANCE is trivial.)
> "Inform: Turing Complete And So Much More."
This really ought to be "Inform: not even Turing powerful!".
--
Gareth Rees
David Given
Michael Naunton <m...@interactive.net> writes:
[...]
> But, given that the ZMachine does not provide infinite data space, you
> can,
> in principle, test if any given program halts.
Here's an example program:
do {
c = getchar();
} while (c != 32);
Does this program halt? Both yes and no depending on the input. It's not
possible to say, definitively, whether it does or not. This is the core of
the Halting Problem.
--
+- David Given ---------------McQ-+ "Those who do not understand Unix are
| Work: d...@tao-group.com | forced to reinvent it, poorly." --- Henry
| Play: dgi...@iname.com | Spencer
+- http://wired.st-and.ac.uk/~dg -+
Andrew Plotkin
> In article <37E85E71...@interactive.net>,
> Michael Naunton <m...@interactive.net> writes:
> [...]
>> But, given that the ZMachine does not provide infinite data space, you
>> can,
>> in principle, test if any given program halts.
> [...]
>
> Here's an example program:
>
> do {
> c = getchar();
> } while (c != 32);
>
> Does this program halt? Both yes and no depending on the input. It's not
> possible to say, definitively, whether it does or not. This is the core of
> the Halting Problem.
No, that has nothing to do with the Halting Problem, I'm afraid.
The Halting Problem is usually stated "Does this program halt *for every
possible input*?" So your program gives a definitive answer.
L. Ross Raszewski
>Philip W. Darnowsky <pdar...@qis.net> wrote:
>> No problem; I've written a program in Inform that can check whether
>> any Inform program terminates in finite time.
>
>It *is* possible to determine in finite time whether or not an Inform
>program that doesn't take input terminates (though not with another
>Inform program, obviously).
>
>This is because Inform programs deal with a finite amount of data.
>There's no mechanism for dynamic allocation of memory, so each Inform
>program has a finite number of possible states (say, N). You can
>determine if the program halts by simulating it for N steps -- after
>which if it hasn't halted then it must have entered a loop and therefore
>will never halt.
>
Well, doesn't this mean that any existing computer can have a similar
testing system made for it? I realize that with dynamic allocation and
virtual memory, modern computers can claim a whole lot of memory, but
even that's _not_ an infinite data space, just a very very large one.
After all, a computer tiself can't dynamically allocate memory -- a
program can just ask the computer to let it use more fo the memory the
computer already has (sort of why there's no dynamic allocation in
the Z machine; it simulates a computer in a sometimes-tragically
accurate way)
Gareth Rees
> Well, doesn't this mean that any existing computer can have a similar
> testing system made for it?
Yes. Any finite computer has a finite number of possible states, so its
halting problem is solvable. (But only in theory -- in practice the
number of states is too big.)
The Turing machine and other abstract definitions of computation gain
their power from the potentially unbounded amount of storage they can
use.
Many programming languages have obvious unbounded analogues -- for
example, we can easily imagine a Lisp in which CONS never fails due to
lack of memory. It's not quite so clear what the unbounded analogue of
Inform would be -- even if Class.new() never fails, there's still the
issue of how to address unboundedly many objects with 16-bit pointers.
--
Gareth Rees
David Given
Andrew Plotkin <erky...@netcom.com> writes:
[...]
>> Does this program halt? Both yes and no depending on the input. It's not
>> possible to say, definitively, whether it does or not. This is the core of
>> the Halting Problem.
>
> No, that has nothing to do with the Halting Problem, I'm afraid.
>
> The Halting Problem is usually stated "Does this program halt *for every
> possible input*?" So your program gives a definitive answer.
Ah. Oops. I appeared to have suffered a pedal-oral interface.
I suspect I may have to pay more attention this time around...
--
+- David Given ---------------McQ-+
| Work: d...@tao-group.com | No lawyers were harmed in the creation of
| Play: dgi...@iname.com | this post. I'll try harder next time.
+- http://wired.st-and.ac.uk/~dg -+
David Glasser
> It *is* possible to determine in finite time whether or not an Inform
> program that doesn't take input terminates (though not with another
> Inform program, obviously).
>
> This is because Inform programs deal with a finite amount of data.
> There's no mechanism for dynamic allocation of memory, so each Inform
> program has a finite number of possible states (say, N). You can
> determine if the program halts by simulating it for N steps -- after
> which if it hasn't halted then it must have entered a loop and therefore
> will never halt.
Hmm. I never thought of it this way; this does make sense.
Does "program" above also include any input to the program? Obviously,
the Inform equivalent of
do {
c = getchar();
} while (c != 'M');
mentioned elsethread could have N 'q's as input followed by one 'M'.
Wouldn't your algorithm say that this program doesn't halt when it does?
Or are you including the input in the amount of states? In that case,
shouldn't input be treated as a potentially infinite stream?
(I'm sure I've missed something, since Gareth obviously knows more than
me.)
--
David Glasser | gla...@iname.com | http://www.davidglasser.net/
rec.arts.int-fiction FAQ: http://www.davidglasser.net/raiffaq/
"So, is that superior artistry, or the easy way out?"
--TenthStone on white canvases as art, on rec.arts.int-fiction
David Glasser
No, the most inciteful description is certainly posting "FICTION IS THE
STUFF THAT IS STOOPID!!!!!" to a fiction newsgroup, or perhaps posting
"SIMULATION IS THE STUFF THAT IS STOOPID!!!!!" to a simulation
newsgroup.
Now, insightful...
</ObSpellingflame>
--
David Glasser | gla...@iname.com | http://www.davidglasser.net/
"It's good to explore the G.U.E. caves / It's good to explore the G.U.E.
caves / You can count all the leaves / You can KILL TROLL WITH SWORD /
You'll get stuck but you won't be bored"-Joe.Mason, rec.arts.int-fiction
Evin Robertson
> Well, doesn't this mean that any existing computer can have a similar
> virtual memory, modern computers can claim a whole lot of memory, but
> even that's _not_ an infinite data space, just a very very large one.
> After all, a computer tiself can't dynamically allocate memory -- a
> program can just ask the computer to let it use more fo the memory the
> computer already has (sort of why there's no dynamic allocation in
> the Z machine; it simulates a computer in a sometimes-tragically
> accurate way)
Well, the computer can always pop a message and tell the user to
install more RAM/swap. Of course, memory is still limited to the
user's budget.
If you have RAIF-POOL installed, the computer installs more memory for
you, robbing banks when it runs out of cash, developing interstellar
travel when the resources of this solar system run out. If you
thought virtual memory was slow when your swap was over NFS, just watch
it crawl when your swap is in another galaxy.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Peter Seebach
David Glasser <gla...@iname.com> wrote:
>Kevin Forchione <Lys...@email.msn.com> wrote:
>
>> This is, perhaps, the most inciteful description of the difference between a
>> simulation and a work of fiction. As I have stated before, memorable stories
>> are not the result of mirroring reality, but of a deft presentation of the
>> most dramatic details.
>
>No, the most inciteful description is certainly posting "FICTION IS THE
>STUFF THAT IS STOOPID!!!!!" to a fiction newsgroup, or perhaps posting
>"SIMULATION IS THE STUFF THAT IS STOOPID!!!!!" to a simulation
>newsgroup.
A play on words worthy of Hitler.
Joe Mason
>Philip W. Darnowsky <pdar...@qis.net> wrote:
>> No problem; I've written a program in Inform that can check whether
>> any Inform program terminates in finite time.
>
>program that doesn't take input terminates (though not with another
>Inform program, obviously).
>
>This is because Inform programs deal with a finite amount of data.
>There's no mechanism for dynamic allocation of memory, so each Inform
>program has a finite number of possible states (say, N). You can
>determine if the program halts by simulating it for N steps -- after
>which if it hasn't halted then it must have entered a loop and therefore
>will never halt.
Proof, please.
I'd disprove it, but I don't have time at the moment. If I haven't done it by
this weekend, somebody remind me.
Joe
Joe Mason
Update: the reason this doesn't work is that the Halting Problem asks whether
the given program halts for EVERY input. So if you give your program input X,
and run it for N+1 cycles, and it doesn't stop, then it'll loop forever - but
only for input X. There are a finite number of states, but there are an
infinite number of possible inputs, so you have to perform the test an
infinite number of times. So the algorithm
for each input
run the program for N+1 cycles
if (program has halted)
return "PROGRAM HALTS"
else
continue
program has not halted -> return "PROGRAM DOES NOT HALT"
can never return "PROGRAM DOES NOT HALT".
It's easy to prove a program halts - just give an example input and run it
till it does. But it's impossible to prove it DOESN'T halt - so if you have a
program, and can't find an instance where it halts, you can't be sure where
it'll never halt, or you just haven't tried the right input.
(Note that I've just showed that Gareth's method doesn't work: I haven't
proved that NO method works. I'll get to that, but not tonight.)
Joe
Gareth Rees
> It *is* possible to determine in finite time whether or not an Inform
> program that doesn't take input terminates (though not with another
> Inform program, obviously).
Joe Mason wrote:
> Update: the reason this doesn't work is that the Halting Problem asks
> whether the given program halts for EVERY input.
There are lots of problems that are equivalent to the halting problem.
One of which is the one you give. Another is "does the program halt
when given no input (for Turing machines, "does the program halt when
started on an empty tape?"). Note my proviso above.
But in fact I don't need the proviso.
PROBLEM H: Given an Inform program, does it halt for every input?
THEOREM: Problem H is PSPACE-complete.
PROOF: First I give an algorithm for solving H. An Inform program has a
finite number of possible states, say N. We maintain a set S of states
accessible to the program from the initial state with some combination
of input. Repeatedly we generate the set S' of states accessible in one
step of execution from a state in S with any possible item of input.
Note that the set S' is bounded in size -- in particular |S'| <= N. If
S' is empty, we know the program halts on every input. If the
intersection between S and S' is non-empty, we know the program loops on
some input (since we've just found a loop). Otherwise let S be S u S'
and repeat. Since there are at most N possible states that the program
can enter, and since |S| increases at each step, the algorithm must
terminate.
To see that the problem is in PSPACE, note that it is in NPSPACE --
simply guess some input that leads to a loop. Then by Savitch's theorem
it is in PSPACE. Completeness follows from the completeness result for
the related problem "Given an Inform program that takes no input, does
it halt?" since we can just throw away all input without looking at it.
--
Gareth Rees
Gunther Schmidl
> If you have RAIF-POOL installed, the computer installs more memory for
> you, robbing banks when it runs out of cash, developing interstellar
> travel when the resources of this solar system run out. If you
> thought virtual memory was slow when your swap was over NFS, just watch
> it crawl when your swap is in another galaxy.
This problem has been addressed by the latest build, now available as a 6 TB
download (or get the 4 GB update only) from the usual channels.
--
+-----------------+---------------+------------------------------+
| Gunther Schmidl | ICQ: 22447430 | IF: http://sgu.home.dhs.org/ |
|-----------------+----------+----+------------------------------|
| gschmidl (at) gmx (dot) at | please remove the "xxx." to reply |
+----------------------------+-----------------------------------+
ct
In article <l6iG3.21627$FW3....@news21.bellglobal.com>,
Joe Mason <jcm...@uwaterloo.ca> wrote:
>Gareth Rees <gar...@cre.canon.co.uk> wrote:
>>This is because Inform programs deal with a finite amount of data.
>>There's no mechanism for dynamic allocation of memory, so each Inform
>>program has a finite number of possible states (say, N). You can
>>determine if the program halts by simulating it for N steps -- after
>>which if it hasn't halted then it must have entered a loop and therefore
>>will never halt.
>
>Proof, please.
>
>I'd disprove it, but I don't have time at the moment.
Seems perfectly correct to me. (Remembering that N is some /massive/
number!) What, after all, can it do at step (N+1)? If it can enter a
state it's not previously been in, I'll be hugely surprised...
regards, ct