Jump to content

Count to 1000 in binary


zx0

Recommended Posts

1010101010

@Dae

That's true, I guess I was giving the answer to a state generator that would halt instead of a set of non-halting programs. As far as I know, this problem is not solved and has been proved uncomputable.

However, a partial way to find the set of programs that would halt on a given input would require computing all possible ways of generating a distinguishable output from a given input and then all mechanisms to halt on the generator's output. This would also include all possible other actions the program could take without modifying the two above steps, and all ways to reorder or merge these three parts. So the partial answer would be the set of all perfect variable sized hash algorithms permuted with the set of all ways to distinguish a specific output in such order that a halt is logically guaranteed. Then this set would then be permuted with itself with the desired input into a new set that verifies both the hardcoded input and the secondary input. This last permutation would be repeated infinitely for the partial solution.

Edited by boink666
Link to comment
Share on other sites

1010101011

HA!!! I'm on the 1's again!

@Job

Look at my answer. My answer is the short version (Turing decidable/Turing recognizable). Now look at boink's answer. That's a very convoluted explanation of my answer ^-^. Computer scientists don't exactly get paid much (whatever the wage of a professor is nowa days), but that doesn't include whatever work they happen to do on the side (which could make them pretty wealthy).

So now you might be able to see that there are some questions that people think CANNOT be computed by any computer or any mathematics. Finding more of these isn't really a focus of study for computer scientists, but it's part. What's usually a hotter topic of research is looking for more efficient ways to do things, and looking for proof that things CANNOT be done more efficiently. Thinking of these kinds of algorithms is what computer scientists do at the doctorate level.

@Boink

As I said above, you basically restated what I meant when I said not Turing decidable but Turing recognizable ^-^. No need to get too technical about it either. The set I derived my problem from is reducable to this set: {<M, w> | M is a Turing Machine and M accepts w} which is not Turing decidable. I don't wanna type out the proofs for any of these -_- but just trust me that they are all proven undecidable. I actually had to go look up in a text book of mine a good undecidable set to base my problem on for illustration purposes xD. Proving this stuff would be going waaaaay too deep for a forum game thread though.

Link to comment
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...
Please Sign In