Oifi

From Esolang
Jump to navigation Jump to search

Oifi ['oi.fi:], which stands for "Output IF Input", is an esolang created by CreeperBomb with the explicit purpose of showing why allowing infiniite program length to find the power of a programming language is dumb and stupid. All Oifi programs are on 2-by-n tables, where n is a natural number or infinity. The exact storage and format method does not matter as long as all characters can be written into the table and the dimensions are as specified. When run, it will ask for user input, and look for that in the right column of the table. If not found, nothing is outputted. If found, then the entry on the left column in the same row will be outputted.

Mild trollage

Oifi would be a completely useless language if not for infinite tables. It is the most total a language can be while not being trivial. Despite this, Oifi is super-TC.

Enter every possible and valid program of a Turing complete language of your choice on input column in a predefined order. On the output column, list whether they halt. Congrats. You have just solved the Halting Problem by writing a program that, in finite runtime, can determine whether any program halts. You can also list the outputs of programs if you only care about a language being just Turing complete.

Some readers may complain that determining what to put in each row requires a super-TC language to simulate the programs, and thus Oifi is not super-TC or TC, but this argument is incorrect. Not knowing how to code, say, a Minsky machine in a programming language does not mean that the language is incomplete - being unable to code a Minsky machine does. Additionally, a halting detecting program can be found with infinite time using a Turing machine (infinite runtime being what allows Turing machines to have a higher computability), so languages that require their infinite programs to be generatable by a program in a TC language are still super-TC.

Conclusion

As infinite program length allows a total(ly useless) language to become super-Turing complete, it can't be used to determine power, even if the program can be generated by something which is only Turing complete.

Example programs

The following is the first few rows of a halting detector for brainfuck. All input is assumed to be the whole BF program. For obvious technical reasons, not all of the rows can be listed, so elispses are inserted at the cut off point.

Halts +
Halts -
Halts >
Halts <
Halts .
Halts ,
Halts ++
Halts +-
Halts +<
Halts +.
Halts +,
Halts -+
Halts --
Halts ->
Halts -<

The following is a number-guessing game (1-64) with a preset answer of the answer to the correct question. Please tell me if you know the question and we can negotiate on how to split the money.

Higher 1
Higher 2
Higher 3
Higher 4
Higher 5
Higher 6
Higher 7
Higher 8
Higher 9
Higher 10
Higher 11
Higher 12
Higher 13
Higher 14
Higher 15
Higher 16
Higher 17
Higher 18
Higher 19
Higher 20
Higher 21
Higher 22
Higher 23
Higher 24
Higher 25
Higher 26
Higher 27
Higher 28
Higher 29
Higher 30
Higher 31
Higher 32
Higher 33
Higher 34
Higher 35
Higher 36
Higher 37
Higher 38
Higher 39
Higher 40
Higher 41
Halts 42
Lower 43
Lower 44
Lower 45
Lower 46
Lower 47
Lower 48
Lower 49
Lower 50
Lower 51
Lower 52
Lower 53
Lower 54
Lower 55
Lower 56
Lower 57
Lower 58
Lower 59
Lower 60
Lower 61
Lower 62
Lower 63
Lower 64

The following should be used to test an interpreter. It is a valid program.