News for hackers. Stuff that matters.
Re:A number that can't be calculated by moomin on Tuesday October 25, 2022 @03:04PM (#33334807)
I think it’s much simpler than that. If you remember your maths well enough to remember the proof that the reals are uncountable and the rationals are countable, consider that the list of programs that produce a number is countable. You don’t need to check if the program halts or not, even if we “count” the “numbers” from the programs that don’t halt _it’s still countable_. But we’re still left with an uncountable set of numbers for which we can’t even write a program.

Easiest way to construct one is to use the diagonal argument that’s used to prove, amongst other things, the halting problem.

Re:A number that can't be calculated by alexmolas on Tuesday October 25, 2022 @03:36PM (#33335136)
yes, I didn't think about it, but you're right! However, I liked the idea to have a constructive way to build an uncomputable number
Re:A number that can't be calculated by kotlin2 on Tuesday October 25, 2022 @03:17PM (#33334936)
You have an assumption that each number needs a unique program to compute the digits. You'd need to prove that statement first.
Re:A number that can't be calculated by sblom on Tuesday October 25, 2022 @03:34PM (#33335112)
By definition, each program only produces the digits of one number. It's okay for more than one program to produce the same number. Am I misunderstanding your point?
Re:A number that can't be calculated by kotlin2 on Tuesday October 25, 2022 @03:48PM (#33335281)
I didn’t realize the initial state of the tape was part of the definition of a Turing machine. I was picturing having the same operations applied to different tapes, but that’s not the definition so I’m wrong.
Re:A number that can't be calculated by craggyjaggy on Tuesday October 25, 2022 @03:32PM (#33335096)
How can the same program produce multiple different results?
Re:A number that can't be calculated by opportune on Tuesday October 25, 2022 @03:50PM (#33335298)
Ah, I wrote the same proof above. I agree this is a much simpler way of proving the existence and size of the uncomputible numbers. The busy beavers problem is just an example of an interesting case