The robbers are getting away, and the cops have to decide whether to wait for them to stop and arrest them, or set up a road block at the state boundary. They do this by trying to predict whether the robbers' program will halt. Please note that this challenge is hard, especially for the cops.
Robbers are represented by programs written in a language called "W""w", which I invented for this challenge, and which I describe below. Ww is easy to implement and relatively easy to reason about. I will provide a reference implementation and a macro preprocessor that allows it to be written in a somewhat human-readable form.
Cops must provide a program (in any language) that takes a robber's Ww program as input, and tries to decide whether it halts or not. A cop submission is invalidated by a robber program for which it returns the wrong answer or fails to terminate.
You must write a program that takes as input programs in the (pre-processd) Ww language. It should attempt to output a truthy value if its input program ever halts, and a falsy value if it doesn't. Your submission should be written in a "real" programming language rather than Ww. In addition to your program, you should provide a clear English explanation of how it works.
A program written in Ww that halts, but for which the cop program does not return a truthy value. (The cops waited at the roadblock while you stopped, changed your identities and went underground.) You must demonstrate that the program halts, either by running it in the reference implementation of W or by proving that it has to halt eventually.
A program written in Ww for which the cop's program returns a truthy value, together with a proof that your program does not halt. (The cops gave chase, but you kept going until you reached the state border, infinitely far away.)
A program written in Ww for which the cop program itself doesn't halt, together with a proof of thisan argument showing that it doesn't halt. (The cops couldn't make up their minds, so theyjust gave up and got some donuts, hoping nobody would notice.)
The Ww language
[To write up later, if I decide to continue this. W is basically a structured programming version of the "register machine" paradigm. There are integer variables that can be incremented or decremented, and there are while loops that stop if a particular variable is zero, and nothing else. The syntax is designed to be very easy to parse; the only tricky thing about implementation is that the variables have to be infinite-precision integers, otherwise it's not Turing-complete. (But infinite-precision ints are easy to implement if you only have to increment and decrement them.) The addition of a simple macro system will allow things like addition and multiplication to be added as higher-level constructs, without the cop programs having to worry about them.]Syntax and semantics
w is a very simple structured programming language whose variables can only be incremented and decremented, and whose only control structure is the while loop. The syntax is designed to be as easy to parse as possible. Here is an example w program. Below I'll describe what it does.
a+ a+ a+
b+ b+
a{
a-
b+
}
There is a preprocessor [to be provided] that, among other things, standardises the whitespace, so that the code above will be formatted like this:
a b
a+ a+ a+ b+ b+ a{ a- b+ }
The first line (provided by the preprocessor) is a list of all the variable names that appear in the program. All variables in w are unsigned infinite-precision integers. (Infinite precision means that they will never overflow. This is very important for Turing-completeness.) A variable name is any combination of the characters a-z, A-Z, 0-9 and _.
The second line is a list of expressions. There are three kinds of expression. The first two are <variablename>+, which increments a variable by 1, and <variablename>-, which decrements it by 1. (For C programmers, think of these as the postfix ++ and -- operators.) Since the variables are unsigned, it is an error to decrement a variable whose value is zero. This will halt the program immediately. (Note that errors are counted as halting for the sake of this challenge.)
The third type of expression is a while loop. Its syntax takes the form {<variable_name>,<expression_list>}. If the variable has value 0, the expression list is skipped. Otherwise, the expression list is executed repeatedly until the variable becomes zero. (If the variable never becomes zero, the program fails to halt.) That's it - there's nothing more to the language than that.
Note that if you split the second line of the preprocessed program at the spaces, each item will either be } or a variable name followed by a symbol, so you can easily pop off the last character to see what kind of expression you're dealing with.
Looking back at the example program, the first line, a+ a+ a+ increments a three times, setting it equal to 3, and the second line sets b to three. The while loop decrements a while incrementing b until a is zero. So the value of a is added to b, and at the end of the program, a is zero and b is equal to five.
Alternative syntax
Optionally, the preprocessor can output w programs as a string representing a Python list. The example program would appear as follows. The first sublist is the list of variables, and the second is a list of lists representing the parse tree.
[["a", "b"], ["a+", "a+", "a+", "b+", "b+", "a{", ["a-", "b+"]]]
Input and output
For the sake of this challenge, we only care whether a program halts or not when given no input, so there is no input or output in the w language as described here. However, if we wanted we could say that a special variable (let's say _) is initialised with the program's input, and the value of the last expression evaluated is the output. If we do this, the language becomes Turing complete in the classical sense. (The proof is left as an exercise to the reader.)
Implementation notes
Implementing W correctly requires the use of infinite-precision integers. However, the only operations these need to support are incrementing and decrementing, which makes them much easier to implement. The reference implementation uses Python's unlimited precision integers.
