2 ms·

My point is that it is _theoretically_ not possible: there is no algorithm that would allow you to build a TM implementing arbitrary requirements. You have to

My point is that it is _theoretically_ not possible: there is no algorithm that would allow you to build a TM implementing arbitrary requirements. You have to use ad-hoc methods but then it is not possible to know your ad-hoc method is correct! So by "flawless" you can only mean "having some property but we cannot say what property it is". Edit: added "flawless" definition

legalcorrection 4y ago
I'm not sure you're getting this. Let's say you want to build a video chat application with all of the same features as Zoom and not a single bug. That is, in fact, possible. Nothing about Rice's Theorem says you can't build a program without bugs. You can build a flawless video chat application. You won't, but you can. How? Very easy. Every time you're about to write code with a bug, don't. Write that same code but without the bug.
- mkleczek 4y ago
  > Every time you're about to write code with a bug, don't. Write that same code but without the bug. This procedure (algorithm) is ill-defined (is not realisable by a TM) as it would require verifying two things: a) the code you are about to write has a bug (ie. has a specific property) b) the code you wrote does not have a bug (ie. has a specific property) Rice's theorem says both are impossible.
  - legalcorrection 4y ago
    Maybe moving to a specific instance of Rice's theorem is clearer. My point is that while he can't solve the halting problem—i.e. he can't reliably determine whether any arbitrary program will halt—an infallible programmer can reliably write his own programs such that they always halt. So, to go back to the original point, you can't reliably determine the correctness of every possible program. But you could, if you were not prone to error like all humans, always write your own programs such that they are always correct.
    - mkleczek 4y ago
      No. From the fact that we know how to write programs that halt you cannot deduce we know how to write programs with arbitrary (or even just useful) property, because there is no general procedure to do that. In other words: you cannot use the algorithm of writing programs that halt to write programs computing nth digit of Pi :)

legalcorrection 4y ago

I'm not sure you're getting this. Let's say you want to build a video chat application with all of the same features as Zoom and not a single bug. That is, in fact, possible. Nothing about Rice's Theorem says you can't build a program without bugs. You can build a flawless video chat application. You won't, but you can. How? Very easy. Every time you're about to write code with a bug, don't. Write that same code but without the bug.

mkleczek 4y ago
> Every time you're about to write code with a bug, don't. Write that same code but without the bug. This procedure (algorithm) is ill-defined (is not realisable by a TM) as it would require verifying two things: a) the code you are about to write has a bug (ie. has a specific property) b) the code you wrote does not have a bug (ie. has a specific property) Rice's theorem says both are impossible.
- legalcorrection 4y ago
  Maybe moving to a specific instance of Rice's theorem is clearer. My point is that while he can't solve the halting problem—i.e. he can't reliably determine whether any arbitrary program will halt—an infallible programmer can reliably write his own programs such that they always halt. So, to go back to the original point, you can't reliably determine the correctness of every possible program. But you could, if you were not prone to error like all humans, always write your own programs such that they are always correct.
  - mkleczek 4y ago
    No. From the fact that we know how to write programs that halt you cannot deduce we know how to write programs with arbitrary (or even just useful) property, because there is no general procedure to do that. In other words: you cannot use the algorithm of writing programs that halt to write programs computing nth digit of Pi :)