Happy Birthday, Alokananda!

Computer Science Level 3

As a tribute, Agnishom plans to generate a BF program that outputs the string Happy Birthday!

He sees that the following program would be the simplest for him to understand: link .

But then after playing around a bit, he discovers that is too profuse and can be done with a simpler code:

1	`-[------->+<]>-.[--->++++<]>+.-[++>-----<]>..+++++++++.-[---->+<]>++.+[->++<]>.-[--->+<]>--.+++++++++.++.------------.----.---.+[--->+<]>+++.-[---->+<]>+++.`

This inspires him to find the shortest BF program that prints Happy Birthday! .

In general, he is willing to write a (Python) program that outputs the shortest BF program that prints a given string.

Will he succeed?

Assume we are running BF on an infinite cell memory and furthermore, our brains are not super-turing.

No, he is attempting the impossible. Yes, but it will take exponential time anyway. Yes, but it will take exponential time unless P=NP. No, BF cannot output all computable strings.

1 solution

Agnishom Chattopadhyay
May 24, 2015

What Agnishom is attempting to do is to determine the Kolmogorov Complexity of a string relative to bf.

This is not computable by a Turing Machine.

(Proof coming soon)

Waiting for the proof desperately!

Lokesh Sharma - 6 years ago

@Lokesh Sharma , See the Kolmogorov Complexity wiki

Agnishom Chattopadhyay - 6 years ago

I am writing an wiki on Kolmogorov Complexity. I'll post the proof there soon.

For now, please see: Wikipedia

This is actually a more formal form for Berry's Paradox

Agnishom Chattopadhyay - 6 years ago

Happy Birthday, Alokananda!

1 solution

0 pending reports