The halting problem, as usually presented, is:

Construct a Turing machine that determines, when given the description
of any Turing machine and initial tape content, whether that Turing
machine with that initial tape content will halt.

This problem statement does not specify how the Turing machine shall
be described nor how the determined result shall be indicated. These
details are left to the solver to design.

In some situations it might be better to be specific about these details.
One way is to refer to define the halting problem corresponding to a
particular universal Turing machine U:

Construct a Turing machine that has the same input aplhabet as U
and halts in the state Y if U with the same initial tape content halts
but otherwise halts in the state N.

This can be expressed a little more formally:

A Turing machine H is the halt decider corresponding to U if for any
input x either H(x) halts in state Y and U(x) halts or H(x) halts in
state N and U(x) does not halt; otherwse H is not the halt decideder
corresponding to U.

Mikko

On Saturday, 23 April 2022 at 22:32:42 UTC+8, Mikko wrote:
> The halting problem, as usually presented, is:
>
> Construct a Turing machine that determines, when given the description
> of any Turing machine and initial tape content, whether that Turing
> machine with that initial tape content will halt.
>
> This problem statement does not specify how the Turing machine shall
> be described nor how the determined result shall be indicated. These
> details are left to the solver to design.
>
> In some situations it might be better to be specific about these details.
> One way is to refer to define the halting problem corresponding to a
> particular universal Turing machine U:
>
> Construct a Turing machine that has the same input aplhabet as U
> and halts in the state Y if U with the same initial tape content halts
> but otherwise halts in the state N.
>
> This can be expressed a little more formally:
>
> A Turing machine H is the halt decider corresponding to U if for any
> input x either H(x) halts in state Y and U(x) halts or H(x) halts in
> state N and U(x) does not halt; otherwse H is not the halt decideder
> corresponding to U.
>
> Mikko

The halting problem is defined for ANY Turing Machine, not any restricted set.

The Halting Problem is easy to understand (formal 'academic' proof is more
difficult). Pete Olcott is a nut and a liar.
He pointed to his 'x86utem operation system' (just a manually abortible semi-debuger
with most of the codes copied from internet) executing the (only) simple C program:

#include <stdint.h>
#define u32 uint32_t

void P(u32 x)
{ if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{ Output("Input_Halts = ", H((u32)P, (u32)P));
}

And says "Eureka! look, there is an infinite loop" that no one can see but the
talented idiot. So he declares H(P,P)==true (or false) and applies his patent.
All PO has is just that several lines of C codes and lots of empty talks.

On 2022-04-25 14:08:25 +0000, wij said:

> On Saturday, 23 April 2022 at 22:32:42 UTC+8, Mikko wrote:
>> The halting problem, as usually presented, is:
>>
>> Construct a Turing machine that determines, when given the description
>> of any Turing machine and initial tape content, whether that Turing
>> machine with that initial tape content will halt.
>>
>> This problem statement does not specify how the Turing machine shall
>> be described nor how the determined result shall be indicated. These
>> details are left to the solver to design.
>>
>> In some situations it might be better to be specific about these details.
>> One way is to refer to define the halting problem corresponding to a
>> particular universal Turing machine U:
>>
>> Construct a Turing machine that has the same input aplhabet as U
>> and halts in the state Y if U with the same initial tape content halts
>> but otherwise halts in the state N.
>>
>> This can be expressed a little more formally:
>>
>> A Turing machine H is the halt decider corresponding to U if for any
>> input x either H(x) halts in state Y and U(x) halts or H(x) halts in
>> state N and U(x) does not halt; otherwse H is not the halt decideder
>> corresponding to U.
>>
>> Mikko
>
> The halting problem is defined for ANY Turing Machine, not any restricted set.

My problem is formally different and distinct from the halting problem.
However, the two problems are related. If H were a solution of my problem
for some U, it would also be a solution to the halting problem.

If restriction that U must be an universal Turing machine is removed we get
a more general problem:

Given a turing machine T, construct a turing machine H with the same input
alphabet so that H with initial tape content I halts in the state Y if
T with the same initial tape content halts but otherwise in the state N.

If T is an universal Turing machine then there is no such H, but there
are Turing machines for which H exists.

Another direction to vary the halting problem is:

Construct a method to determine whether a Turing machine halts with every
initial tape content.

Or:

Construct a method to determine whether a Turing machine halts with some
initial tape content.

Mikko

On 4/23/2022 8:32 AM, Mikko wrote:
> The halting problem, as usually presented, is:
>
>  Construct a Turing machine that determines, when given the description
>  of any Turing machine and initial tape content, whether that Turing
>  machine with that initial tape content will halt.
>
> This problem statement does not specify how the Turing machine shall
> be described nor how the determined result shall be indicated. These
> details are left to the solver to design.
>
> In some situations it might be better to be specific about these details.
> One way is to refer to define the halting problem corresponding to a
> particular universal Turing machine U:
>
>  Construct a Turing machine that has the same input aplhabet as U
>  and halts in the state Y if U with the same initial tape content halts
>  but otherwise halts in the state N.
>
> This can be expressed a little more formally:
>
>  A Turing machine H is the halt decider corresponding to U if for any
>  input x either H(x) halts in state Y and U(x) halts or H(x) halts in
>  state N and U(x) does not halt; otherwse H is not the halt decideder
>  corresponding to U.
Why do you think the symbolic representation of TMs would influence
whether HP is true? To be a TM model with a representation, one must be
able to show equivalence between the set of "machines" definable in that
formalism and (any one of) the standard TM models.
So if "Halting?" were computable in one model it would be in another.
As to how the results are to be judged, one must first nail down what
"Halting?" means. Choices I've seen are 1) enters a halt state from
which there is no transition defined for the current instantaneous state
or 2) enter any state for which there is no transition defined for the
current instantaneous state. Using either definition, information might
be conveyed by which state, if any, is final for a given computation.
Theoretically, one is given a machine definition and an initial tape
content. From that, a sequence of states is mathematically defined in
the same sense that "2^i, i >= 0" defines "1 2 4 ....". Halting is
determined by asking the following "Is that sequence finite and, if so,
is the last state in the set of halting states?". This is for definition
of halting 1 in previous paragraph. "Is sequence finite?" is the
criteria for definition 2 above.
Note that the definition and detection of halting has nothing what so
ever to do with the definition of a UTM. For every representation of TM,
there exists a UTM for that representation and a mapping to similar
artifacts in any other TM representation.
Don't worry about being able to achieve different classes of halting
computations with the different halting definitions above. You can not.
I only mention this definition issue since the two have been confounded
for years in this USENET group. As a famous basketball announcer used to
say "No harm, no foul, no blood, etc,".
As to all the above, the real question is the first one: "Why do you
think the symbolic representation of TMs would influence whether HP is
true?"
A suggestion is to look at the proofs of equivalence between/among TM,
Post correspondence problem, Church lambda calculus, and so on. Wildly
different ways of achieving full Turing compute power and all have
equivalent power and halting problems. Some of this stuff is available
in Linz, the book everyone here has been citing for years.
--
Jeff Barnett

On 2022-04-26 17:49:21 +0000, Jeff Barnett said:

> Why do you think the symbolic representation of TMs would influence
>
> whether HP is true?

The question is ill posed as it contains a false assumption so to
attempt to answer it would not be correct.

Mikko