The challenge of self-reference. (Recreational computing) Michael W. Ecker.

The Challenge of Self-Reference

Greetings! Welcome to "Recreational Computing,' anew column which will appear regularly in Creative Computing. We will play, explore, challenge, as well as form conjectures, test them, and just plain have good programming fun.

I would especially like to invite all readers to try the challenges, come up with your own solutions, and your own problems as well. They should be recreational in nature. Digit delving and other forms of "microcomputer mathemagic' in Basic are what I have foremost in mind, but I wish to hear from you. Your ideas, if used, will be acknowledged in this column. I solicit your new problems, programs, improved solutions, etc. I will also answer readers who have pertinent questions and who supply a SASE. You may write to me directly: Michael W. Ecker, Ph.D., Contributing Editor, Creative Computing, 129 Carol Dr., Clarks Summit, PA 18411.

Please try to keep your solutions in generic Basic (Microsoft), and as machine-independent as possible. For those who wish to send longer programs, please note that I do not have time to type in long listings, so if you have one of the following machines, magnetic media submissions are welcome: I have a TRS-80 Model 3 with 48K and two disk drives and tape, a TRS-80 Model 4P with 128K and two disk drives, and a Sanyo MBC-555 with 256K and two single-sided drives under MS-DOS 1.25 only. The Sanyo can read IBM PC Basic programs if you save them in ASCII format on one side only. I do have access to other machines, including IBM PCs, but these are less convenient.

Please also feel free to keep the editors aware of your interest so that we can see whether there is sufficient interest for an expanded column. I think you will be pleased to know that this column is partially a result of a survey taken earlier by Creative Computing in which you readers indicated interests beyond the ordinary business applications so prevalent in other magazines. Credit Creative and David Ahl for responding to your wishes. And now, off to our first problem.

Last year, Andy Bulfer of New Jersey wrote to me and posed the following very interesting challenge. It might not be brand new, but it is a natural one that you will enjoy. Write a program which, when run, produces an exact listing of the program itself--no more and no less. Worded that way, of course, there is an easy solution. Think about it before you read on.

Have you thought about it? The trivial solution is a one-liner:

10LIST

but somehow that hardly seems sporting. Suppose we insist on a solution that will run on as many machines as possible (no PEEKS OR POKES, CALLS, machine language subroutines, input, etc.) and which does not allow the LIST command. Can you find a solution then? Next time I will publish one of Dr. Bulfer's ingenious solutions.

The explanation behind the title this month lies in the analogous situation with logical puzzles. The prototype of these is Russell's Paradox. One version of this goes as follows: Sal is a barber in the town of Seville. His clients are precisely all the barbers of Seville who do not shave themselves; nobody else is a client. The question is: Who shaves Sal?

If Sal shaves himself, then he must be one of his own clients, since he shaves nobody else. That makes him, by construction, a barber who doesn't shave himself. Hence, if he shaves himself, he doesn't shave himself.

On the other hand, if Sal doesn't shave himself, he is a barber of Seville who doesn't shave himself. But that makes him one of his own clients. Hence, Sal shaves Sal. It follows that if he doesn't shave himself, then he does.

In summary, we have a paradox: he shaves himself if and only if he doesn't!

The element of self-reference may be thought of as the culprit. Actually, the real problem lies in the inadmissible mixture of ordinary language (object language) with language about language (metalanguage). You may see this more clearly with this easier example: This sentence is false.

Is that true or false? Again, if true, then it's true that it's false, so it's false. But if it's false, then it's false that it's false, so it must be true. In other words, a paradox: it's true if and only if it's false. The problem is the intermingling of metalanguage (to judge truth or falsity) and object language (used for ordinary sentences, the ones about which judgments may be later made).

In the world of programming, running applications is analogous to using language. Editing and listing are analogous to using metalanguage (language or devices to act on the language--the listing--itself).

This programming challenge should provide some good food for thought. Next time I will show Dr. Bulfer's very interesting solution, which he wrote for an Apple computer. I should point out that, very strictly speaking, most other computer owners will not be able to solve this 100%-- about 99% maybe. The reason for this is that the Basic interpreter on an IBM PC, a TRS-80, a Sanyo 550 or 555, and many other machines with Microsoft Basic, inserts an additional space in front of numbers. If you use one of these computers and have the command:

Print "10 Print (message)' upon execution, you will get your 10 Print (message), but you will note that the first digit, 1, is printed in the second column on your screen, not the first. The listing, however, will always be printed out flush left. I doubt that we can do anything about that, however. Next time I will give the solution with the modification and indicate what to change for you more fortunate (in this one case, that is) Apple owners.

Until next month, happy recreational computing!