Compute the uncomputable ... sort of

Question

Implement a function \$f\$ (as a function or complete program), such that

\$ \displaystyle\lim_{n\rightarrow \infty} f(n) \$

converges to a number which is not a computable number.

Answers will be scored in bytes with fewer bytes being better.

IO formats

Your answer may be in any of the following formats

• A program or function that takes \$n\$ as input and outputs \$f(n)\$.
• A program or function that takes \$n\$ as input and outputs all \$f(m)\$ where \$m \leq n\$.
• A program or function that outputs successive members of the sequence indefinitely.

Numeric output can be given as any of the following

• An arbitrary precision rational type.
• A pair of arbitrary precision integers representing a numerator and denominator. e.g. \$(2334, 888)\$
• A string representing a rational expressed as a fraction. e.g. 2334/888
• A string representing a rational expressed as a decimal expansion. e.g. 3.141592

Use of fixed precision floating point numbers is unfortunately not accepted. They end up being messy when dealing with limits, I hope the options permitted allow the majority of languages to compete in this challenge relatively unencumbered.

Neither of the fractional outputs are required to be in reduced form.

Examples

Here are some numbers which are not computable, but are computable in the limit. That is any of the following numbers are potential limits for valid solutions to the challenge. This list is obviously not exhaustive.

• The real whose binary expansion encodes the halting problem.
• The real whose binary expansion encodes the busy beaver numbers.
• The real whose binary expansion encodes the truth set of first order logic.
• Chaitin's constant

Example algorithm

The following is an example algorithm which solves the problem by converging to the first example.

Take a positive integer \$n\$ as input. Take the first \$n\$ Turing machines and run each of them for \$n\$ steps. Output

\$ \displaystyle\sum_{m=0}^n \begin{cases}2^{-m}& \text{if machine }m\text{ halted before }n\text{ steps}\\0 & \text{otherwise}\end{cases} \$

That is to say we start at zero and add \$1/2^m\$ for each machine \$m\$ that halts in our simulation.

Now since computing a Turing machine for \$n\$ steps is computable, and adding rational numbers certainly is computable, this algorithm is as a whole computable. However if we take the limit, we get a string that exactly encodes the solutions halting problem. The limit is:

\$ \displaystyle\sum_{m=0}^\infty \begin{cases}2^{-m}& \text{if machine }m\text{ halts}\\0 & \text{otherwise}\end{cases} \$

I think it is intuitive that this sort of thing is not something that can be computed. But more concretely if we were able to compute this number then we could use it to solve the halting problem, which is not possible.

Answer 1

05AB1E, 25 24 bytes

LεÅγιøIãʒηεøJË}à}gĀ}'.šJ

Try it online!

-1 thanks to @ovs

f(n) is a decimal number such that it's xth digit is 1 iff x<=n and when you run length encode x and convert it to matching pairs, it has a solution to PCP with a length of at most n pairs.

outputs as .digits after the dot. In case the 0 is needed, it's +1 to replace '. with „0.

Code explaination:

L      all numbers from 1 to N
ε      map each to
 Åγ    run length encode
 ι     uninterleave to two lists
 ø     tranpose
 Iã    cartesian power N, all choices of N such pairs
 ʒ     only keep those such that
  η    its prefixes
  ε    map each to
   ø   itself transposed
   J   joined
   Ë   both elements are equal
  }
  à    maximum - if any of those are 1
 }
 gĀ    the length of the filtered list isn't 0
}
'.š    prepend .
J      join, and implicitly print

We can show a reduction from PCP with two symbols (which is known to be undecidable):

given an instance of PCP with two symbols, 1 and 2 (for example [2,1], [11,2], [2212,111]), unflatten the pairs (which would give [2,1,11,2,2212,111] in the example) and run length decode with alternating 1, 0. That number would be x. The solution to the PCP instance is 1 iff the xth digit of the limit of this function is 1.

Answer 2

Python 2, 189 188 186 bytes

-2 thanks to @Wheat Wizard

from itertools import*
j=input()
s='.'
for x in range(j):d=`x`.split('0');s+='X10'[min(len(set(map(''.join,zip(*l))))for l in product(*[[d[i:i+2]for i in range(0,len(d),2)]]*j))]
print s

Try it online!

A port of my 05AB1E answer to python, using a 0 seperator instead of run length encoding.

Answer 3

Vyxal, 34 32 bytes

ƛ0€y"ÞT:£⁰(¥J)ṖƛKƛÞTƛṅ;≈;a;a;\.p

-2 thanks to @Aaron Miller

Try it Online!

This is a port of my 05AB1E answer, with seperating by 0 instead of run length decoding required, and a different behavior when the length of it isn't even. Also, instead of up to N pieces, it's up to N uses of each piece, but all of that shouldn't matter to the limit's uncomputablity. This is my first time golfing in vyxal, so any improvements would be helpful.

ƛ         map each in range to
 0€       split by 0
 y"ÞT     uninterleave and transpose
 :£       save in register
 ⁰(¥J)    merge with itself input times
 Ṗ        take all permutations
 ƛ        and map each to
  K       its prefixes
  ƛ       map each to
   ÞT     it transpose
   ƛṅ;    join each
   ≈      all are equal?
   ;
   a      are any of those 1?
  ;
  a       are any of those 1?
;
\.p       prepend .
implicitly output as a string