= 27d567bc2d48d9f40e9ccc20ea370b15)
benelliott comments on Complexity and halting - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (8)
Does anyone know if the following are equivalent:
An oracle that returns the length of the shortest program to return a given string of bits.
An oracle that returns the length of the shortest program to return either the given string of digits or any longer string that begins with the given string.
More specifically, is there an algorithm that computes the latter by consulting the former.
If the answer to this is yes then the answer to the problem in the OP is yes as well.