Codegolf - Вычисление Невычислимого... Вроде

Реализуйте функцию \$f\$ (как функцию или полную программу), такую ​​что

\$

\displaystyle\lim_{n\rightarrow \infty} f(n) \$ сходится к числу, которое нет.

а

вычислимое число

Ответы будут оцениваться в байтах, чем меньше байтов, тем лучше.

• форматы ввода-вывода
• Ваш ответ может быть в любом из следующих форматов
• Программа или функция, которая принимает на вход \$n\$ и выводит \$f(n)\$.

Программа или функция, которая принимает на вход \$n\$ и выводит все \$f(m)\$, где \$m \leq n\$.

• Программа или функция, которая бесконечно выводит последовательные члены последовательности.
• Числовой вывод может быть задан как любой из следующих
• Рациональный тип произвольной точности. 3.141592
• Пара целых чисел произвольной точности, представляющих числитель и знаменатель. например \$(2334, 888)\$ 2334/888

Строка, представляющая рациональное число, выраженное в виде дроби. например

Строка, представляющая рациональное число, выраженное в виде десятичной дроби. например

К сожалению, использование чисел с плавающей запятой фиксированной точности не допускается. В конечном итоге они оказываются запутанными при работе с ограничениями. Я надеюсь, что разрешенные варианты позволят большинству языков конкурировать в этой задаче относительно беспрепятственно.

Ни один из дробных выходов не обязан быть в сокращенной форме. ПримерыВот некоторые числа, которые не вычислимы, но

• вычислимый в пределе
• . То есть любое из следующих чисел является потенциальным пределом допустимого решения проблемы. Этот список, очевидно, не является исчерпывающим.
• Реальное, двоичное расширение которого кодирует проблему остановки.
• Настоящее, двоичное расширение которого кодирует числа занятых бобровых.

Реальное, двоичное расширение которого кодирует набор истинности логики первого порядка.

постоянная Чайтина

Пример алгоритма

Ниже приведен пример алгоритма, который решает проблему путем перехода к первому примеру.

Возьмите в качестве входных данных целое положительное число \$n\$. Возьмите первые \$n\$ машины Тьюринга и запустите каждую из них на \$n\$ шагов. Выход

\$

\displaystyle\sum_{m=0}^n \begin{cases}2^{-m}& \text{если машина }m\text{ остановлена ​​до }n\text{ шагов}\\0 & \text{иначе }\end{случаи}

\$

То есть мы начинаем с нуля и добавляем \$1/2^m\$ для каждой машины \$m\$, которая останавливается в нашей симуляции.

05AB1E, 25 24 байта

 
 
 
 
 ƛ         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
 
 
 
 
 

Попробуйте онлайн!

-1 спасибо @ovs

f(n) - это десятичное число, такое, что его x-я цифра равна 1, если x<=n, и когда вы запускаете кодирование длины x и преобразуете его в совпадающие пары, у него есть решение PCP длиной не более n пар.

выводит как ƛ0€y"ÞT:£⁰(¥J)ṖƛKƛÞTƛṅ;≈;a;a;\.p . In case the 0 is needed, it's +1 to replace 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 с 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

Объяснение кода:

Мы можем показать приведение к PCP с двумя символами (которые, как известно, неразрешимы):

учитывая экземпляр PCP с двумя символами, 1 и 2 (например, [2,1], [11,2], [2212,111]), разгладьте пары (что даст [2,1,11,2, 2212,111] в примере) и декодировать длину серии с чередованием 1, 0. Это число будет x. Решение экземпляра PCP равно 1, если x-я цифра предела этой функции равна 1.

Питон 2, 189 188 186 байт

-2 спасибо @Wheat Wizard

Попробуйте онлайн!

Порт моего ответа 05AB1E на Python с использованием разделителя 0 вместо кодирования длины серии.

Виксал, 34 32 байта

-2 спасибо @Aaron Miller

Попробуйте онлайн!

Это порт моего ответа 05AB1E, с разделением на 0 вместо требуемого декодирования длины серии и другим поведением, когда его длина нечетная. Кроме того, вместо N штук каждая фигура может быть использована до N, но все это не должно иметь значения из-за невычислимости предела. Я впервые играю в гольф в Выксале, поэтому любые улучшения будут полезны.