Golficator

Golficator is a computational model invented by User:Hakerh400. This computational model is designed to be able to convert any Turing-complete language into a golfing language.

Overview

Given a Turing-complete language $ L $, we describe the process of constructing a new language $ L' $.

First create the list of all syntactically valid programs in $ L $ sorted in some way. Each program in the list represents a mapping from strings to strings.

Then remove from the list all programs that throw an error for at least one input or do not halt for at least one input. Then remove duplicates, that is, remove each program whose input-output mapping is identical to some program that appears before in the list.

The list now contains unique programs. Each program in the list halts for all inputs and each program represents a unique input-output mapping.

Each program in $ L' $ consists of a single non-negative integer that represents the index in the list. We simply pick the program for that index and execute it as an $ L $ program.

Computational class

The process of constructing $ L' $ is uncomputable. However, $ L' $ itself is computable, but since all programs halt, it is a total language so it is not Turing-complete.

Characteristics

Language $ L' $ is much more suitable for golfing purposes, because useless programs are removed (the ones that throw an error or do no halt, though non-halting arguably arent useless). Also, there are no duplicate programs, so each program can do some new useful stuff. Since the integer in $ L' $ can be represented in any way, we can encode it as an array of bytes to make it more compact.

Implementation

Unfortunately, Golficator is unimplementable on a Turing-machine. However, assuming the consistency of some mathematical system and picking a good $ L $ to start with, we can more-or-less manually construct the beginning of the list, so we can actually do the computation for some short programs.