Tom's JavaScript Machine

[ Machine | Instructions | Examples | JavaScript Basics | Challenge | Hints | About ]

The Generalized Challenge

This challenge is a generalization of the (first) Challenge, which we assume you have completed. It was already briefly stated in the Afterthoughts on the first Challenge. Here is a more complete description of the Generalized Challenge:

Write a program G for Tom's JavaScript Machine

• that takes as input any valid JavaScript definition of a function f that takes a string as argument, and
• that produces as output a valid JavaScript program P_f
• such that the program P_f behaves like the function f applied to the program P_f itself, that is, like f(P_f).

This Generalized Challenge will lead you into the heart of the foundations of theoretical computer science. In particular, at the end of the accompanying hints we will consider a very special function f related to the (hypothetical) halting function H. This function takes as argument a string with a JavaScript program and supposedly returns whether execution of this program, without input, halts.

Notes:

• Function f can read input and do ouput; it need not return a value (that value is irrelevant). However, program P_f should read no other input than f does.
• More specifically, to 'behave like' does not mean that the programs do exactly the same internal calculation steps, but it does require that P_f and f(P_f) are indistinguishable in their externally observable behavior, that is, in the input and output that they do.
• The program P_f is a fixed point of function f , because f(P_f) = P_f, where equality is behavioral equivalence. The existence of program G proves that every valid JavaScript function on strings has a (behavioral) fixed point. Also see David Madore's Discussion of Quines.
• By taking for f the following definition:
  the program P_f output by G is a self-reproducing program, because f(P_f) just outputs P_f; Hence, P_f outputs itself, and thus it is a solution to the first challenge. Therefore, the first challenge is a special case of the new challenge; the new challenge generalizes the first challenge.
• A slightly simpler version of the Generalized Challenge concerns a program that, given a function g from strings to strings, constructs a program Q_g that processes no input and that outputs g(Q_g).

  Applying the Generalized Challenge to f with definition

  yields a program P_f that can serve as Q_g

As with the first challenge, you are encouraged to write a program

1. that uses only these JavaScript basics and extensions,
2. that adheres to reasonable coding conventions, in particular, source lines must be no longer than 80 characters (this makes for a more interesting challenge), and

These requirements could be dropped initially, but using extra JavaScript features is not necessary and can be distracting. User-defined functions can be helpful, as well as the predefined constants QU and NL.

In case you get stuck, you can look at some hints.