Is it possible to determine if a Turing machine, which starts with an
empty tape, halts?

On Sunday, October 30, 2022 at 12:02:45 PM UTC-4, Newberry wrote:
> Is it possible to determine if a Turing machine, which starts with an
> empty tape, halts?

No, the Turing machine could "have the input hard-coded into it," so Turing's proof still applies. One way it could be done is, the machine could output its "starting input," in a different version, right away, and then run the main part of the machine on the now-outputted input. Thus, any pair M, I of Turing machine and input can be equivalently represented, computationally, with TMs with an empty tape...so the Halting Problem proof still applies. In particular, since it is computable to map every M, I pair to a TM with no input, and back, we have that if the problem you describe were computable, the Halting Problem would be solvable. That's a contradiction, so we have our result.

-Philip White (philipwhite363@gmail.com)

On Sun, 30 Oct 2022 09:15:34 -0700 (PDT)
Philip White <philipwhite363@gmail.com> wrote:

> On Sunday, October 30, 2022 at 12:02:45 PM UTC-4, Newberry wrote:
> > Is it possible to determine if a Turing machine, which starts with
> > an empty tape, halts?
>
> No, the Turing machine could "have the input hard-coded into it," so
> Turing's proof still applies. One way it could be done is, the
> machine could output its "starting input," in a different version,
> right away, and then run the main part of the machine on the
> now-outputted input. Thus, any pair M, I of Turing machine and input
> can be equivalently represented, computationally, with TMs with an
> empty tape...so the Halting Problem proof still applies. In
> particular, since it is computable to map every M, I pair to a TM
> with no input, and back, we have that if the problem you describe
> were computable, the Halting Problem would be solvable. That's a
> contradiction, so we have our result.

That presupposes that the Halting Problem is not solvable.
Presupposition is a logical fallacy if the assumption is not based on
an axiom.

/Flibble

On 10/30/2022 11:02 AM, Newberry wrote:
> Is it possible to determine if a Turing machine, which starts with an
> empty tape, halts?

Yes as proven below:

// rec routine P
// §L :if T[P] go to L
// Return §
// https://academic.oup.com/comjnl/article/7/4/313/354243
void Strachey_P()
{ L: if (T(Strachey_P)) goto L;
return;
}

int main()
{ Output("Input_Halts = ", T(Strachey_P));
}

_Strachey_P()
[00001962] 55 push ebp
[00001963] 8bec mov ebp,esp
[00001965] 6862190000 push 00001962
[0000196a] e823fdffff call 00001692
[0000196f] 83c404 add esp,+04
[00001972] 85c0 test eax,eax
[00001974] 7402 jz 00001978
[00001976] ebed jmp 00001965
[00001978] 5d pop ebp
[00001979] c3 ret
Size in bytes:(0024) [00001979]

_main()
[000019f2] 55 push ebp
[000019f3] 8bec mov ebp,esp
[000019f5] 6862190000 push 00001962
[000019fa] e893fcffff call 00001692
[000019ff] 83c404 add esp,+04
[00001a02] 50 push eax
[00001a03] 6893060000 push 00000693
[00001a08] e8a5ecffff call 000006b2
[00001a0d] 83c408 add esp,+08
[00001a10] 33c0 xor eax,eax
[00001a12] 5d pop ebp
[00001a13] c3 ret
Size in bytes:(0034) [00001a13]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[000019f2][00102a47][00000000] 55 push ebp
[000019f3][00102a47][00000000] 8bec mov ebp,esp
[000019f5][00102a43][00001962] 6862190000 push 00001962
[000019fa][00102a3f][000019ff] e893fcffff call 00001692

T: Begin Simulation Execution Trace Stored at:112af3
Address_of_T:1692
[00001962][00112ae3][00112ae7] 55 push ebp
[00001963][00112ae3][00112ae7] 8bec mov ebp,esp
[00001965][00112adf][00001962] 6862190000 push 00001962
[0000196a][00112adb][0000196f] e823fdffff call 00001692
T: Infinitely Recursive Simulation Detected Simulation Stopped

[000019ff][00102a47][00000000] 83c404 add esp,+04
[00001a02][00102a43][00000000] 50 push eax
[00001a03][00102a3f][00000693] 6893060000 push 00000693
[00001a08][00102a3f][00000693] e8a5ecffff call 000006b2
Input_Halts = 0
[00001a0d][00102a47][00000000] 83c408 add esp,+08
[00001a10][00102a47][00000000] 33c0 xor eax,eax
[00001a12][00102a4b][00000018] 5d pop ebp
[00001a13][00102a4f][00000000] c3 ret
Number of Instructions Executed(537) == 8 Pages

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Newberry <newberryxy@gmail.com> writes:

> Is it possible to determine if a Turing machine, which starts with an
> empty tape, halts?

Sometimes. If you mean is there are algorithm that is always correct,
then the answer is no.

--
Ben.

On 10/30/2022 11:30 AM, Ben Bacarisse wrote:
> Newberry <newberryxy@gmail.com> writes:
>
>> Is it possible to determine if a Turing machine, which starts with an
>> empty tape, halts?
>
> Sometimes. If you mean is there are algorithm that is always correct,
> then the answer is no.
>

It is really great that you stopped the nonsense rebuttals of my work,
thanks.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 10/30/2022 11:15 AM, Philip White wrote:
> On Sunday, October 30, 2022 at 12:02:45 PM UTC-4, Newberry wrote:
>> Is it possible to determine if a Turing machine, which starts with an
>> empty tape, halts?
>
> No, the Turing machine could "have the input hard-coded into it," so Turing's proof still applies. One way it could be done is, the machine could output its "starting input," in a different version, right away, and then run the main part of the machine on the now-outputted input. Thus, any pair M, I of Turing machine and input can be equivalently represented, computationally, with TMs with an empty tape...so the Halting Problem proof still applies. In particular, since it is computable to map every M, I pair to a TM with no input, and back, we have that if the problem you describe were computable, the Halting Problem would be solvable. That's a contradiction, so we have our result.
>
> -Philip White (philipwhite363@gmail.com)

So you don't understand that Sipser_D presents the non-halting behavior
of recursive simulation to simulating halt decider Sipser_H ?

int Sipser_D(int (*M)())
{ if ( Sipser_H(M, M) )
return 0;
return 1;
}

//
// Sipser_H returns 1 when its input would halt and return 1
// otherwise Sipser_H returns 0
//
int Sipser_H(int (*M)(), int (*w)())

When H correctly simulates D it finds that D remains stuck in recursive
simulation
(a) D calls H that simulates D with an x86 emulator
(b) that calls a simulated H that simulates D with an x86 emulator
(c) that calls a simulated H that simulates D with an x86 emulator ...
Until the executed H recognizes this repeating state, aborts its
simulation of D and returns 0.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer