Re: functions that halt
From: Barb Knox (see_at_sig.below)
Date: 04/16/04
- Next message: |-|erc: "Re: functions that halt"
- Previous message: John Doe: "Re: Advice for undergraduate schools?"
- Maybe in reply to: |-|erc: "functions that halt"
- Next in thread: |-|erc: "Re: functions that halt"
- Reply: |-|erc: "Re: functions that halt"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 16 Apr 2004 10:18:37 +1200
In article <407E4EFC.95362B72@msgid.michael.mendelsohn.de>,
Michael Mendelsohn <keine.Werbung.1300@msgid.michael.mendelsohn.de> wrote:
>The Ghost In The Machine schrieb:
>> In sci.logic, |-|erc
>> > Does it disprove Barbs diagnonalistion attack on a theory of
>> > guaranteed halting functions being equivalent in power to the
>> > class of TMs?
>>
>> Yes, as the diagonalization function cannot be placed in a TM.
>
>Oh, but it can.
>
>The point of the guaranteed halting functions (GHF) is that you *can*
>enumerate them, i.e. you can write a function that gives you the k'th
>GHF.
No you can't. That was the whole point of the diagonal proof I posted
originally:
IF there were some total F such that F(i) = an encoding of the i'th total
function on N->N (the i'th "GHF" in your terms), then any diagonal DF
constructed so that DF(j) =/= F(j)(j) is clearly not in the F list -- for each
F(i), DF is different from it (in particular, it is guaranteed to be different
for input i).
>If you grant a mechanism that allows to to actually call such a
>function, or, what amounts to the same thing, "emulate" it (i.e. parse
>it and see what it does), you can write the diagonalisation function
>(DF).
Exactly right. And of course you *can* emulate it (e.g. via a Universal
Turing Machine).
>The only problem is that you can't guarantee the DF to halt if it is a
>GHF,
?? By *definition*, a total function (a "GHF") is guaranteed to halt on all
inputs. So if DF is a total function then it clearly must halt, even when the
input is an encoding of itself.
>because it then calls itself (or a simile of itself) in an infinite
>recursion.
No it doesn't.
>In other words, there is no contradiction if the diagonalisation
>function is not a GHF.
That would be true, but BY CONSTRUCTION of DF it *is* a total function, since
it's simply a slightly modified version of F, which is ASSUMED (incorrectly it
turns out) to be a total function.
But you're making progress (unlike, e.g., "Herc", who has ideological reasons
for refusing to understand diagonal arguments in general).
>Michael
-- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | | B B a a r b b | | BBB aa a r bbb | -----------------------------
- Next message: |-|erc: "Re: functions that halt"
- Previous message: John Doe: "Re: Advice for undergraduate schools?"
- Maybe in reply to: |-|erc: "functions that halt"
- Next in thread: |-|erc: "Re: functions that halt"
- Reply: |-|erc: "Re: functions that halt"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
