473,699 Members | 2,143 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Solution to the halting Problem?

117 7208
"Peter Olcott" <ol****@worldne t.att.net> wrote in message
news:qG******** *************@b gtnsc04-news.ops.worldn et.att.net...
www.halting-problem.com


Off-topic, but I'll bite.

I went to that link expecting a lot more than I found. I was expecting a
very thorough proof that showed that the Halting Problem had a flaw. I kept
re-reading the page because I thought that I had missed something. I guess
I didn't, because all I found was a way to modify or create a program so
that it is possible to know if it will halt. Even then, the second
objection listed on that page shows that it doesn't always work. If I
misunderstood the solution, then feel free to correct me.

The first link on that page defines the halting problem very clearly: No
program can ever be written to determine whether any arbitrary program will
halt. The key phrase here is "any arbitrary." If you try to refute the
claim by modifying the code, then you cannot claim that your solution works
for an arbitrary program. When the claim says arbitrary, it means any
program that could ever exist. Limiting the considered programs to special
cases does not refute the claim. It is very easy for anyone to produce
special cases where it is certain that the program will halt.

In short, your assertion that the "possibilit y of creating one or more
instances of WillHalt() that permit LoopIfHalts() to function does not
refute this method" is incorrect. The meaning of "any arbitrary" is not
negotiable. Like I said, if I misunderstood what that link was trying to
say, correct me. I'm very tired right now and it's possible that I
misinterpreted something.

Nice domain, though.

--
David Hilsee
Jul 22 '05 #2
On Wed, 21 Jul 2004 02:38:14 GMT, "Peter Olcott"
<ol****@worldne t.att.net> wrote:
www.halting-problem.com


What's this got to do with standard C++?

Tom
Jul 22 '05 #3

"David Hilsee" <da************ *@yahoo.com> wrote in message news:w5******** ************@co mcast.com...
"Peter Olcott" <ol****@worldne t.att.net> wrote in message
news:qG******** *************@b gtnsc04-news.ops.worldn et.att.net...
www.halting-problem.com
Off-topic, but I'll bite.

I went to that link expecting a lot more than I found. I was expecting a
very thorough proof that showed that the Halting Problem had a flaw. I kept
re-reading the page because I thought that I had missed something. I guess
I didn't, because all I found was a way to modify or create a program so
that it is possible to know if it will halt. Even then, the second
objection listed on that page shows that it doesn't always work. If I
misunderstood the solution, then feel free to correct me.

The first link on that page defines the halting problem very clearly: No
program can ever be written to determine whether any arbitrary program will
halt. The key phrase here is "any arbitrary." If you try to refute the
claim by modifying the code, then you cannot claim that your solution works
for an arbitrary program.


It works FOR any arbitrary program. It does not work WITH any
arbitrary program. The original analyzer had to be changed. Now
every program analyzed will result in Halting or Not Halting, as long
as the security of the solution has not been violated. If it has been
violated, then after this has been corrected. it will now work with
the program that it did not work for.
When the claim says arbitrary, it means any
program that could ever exist. Limiting the considered programs to special
cases does not refute the claim. It is very easy for anyone to produce
special cases where it is certain that the program will halt.

In short, your assertion that the "possibilit y of creating one or more
instances of WillHalt() that permit LoopIfHalts() to function does not
refute this method" is incorrect. The meaning of "any arbitrary" is not
negotiable. Like I said, if I misunderstood what that link was trying to
say, correct me. I'm very tired right now and it's possible that I
misinterpreted something.

Nice domain, though.

--
David Hilsee

Jul 22 '05 #4
On Wed, 21 Jul 2004 12:04:55 GMT, "Peter Olcott"
<ol****@worldne t.att.net> wrote:
The first link on that page defines the halting problem very clearly: No
program can ever be written to determine whether any arbitrary program will
halt. The key phrase here is "any arbitrary." If you try to refute the
claim by modifying the code, then you cannot claim that your solution works
for an arbitrary program.


It works FOR any arbitrary program. It does not work WITH any
arbitrary program. The original analyzer had to be changed. Now
every program analyzed will result in Halting or Not Halting, as long
as the security of the solution has not been violated. If it has been
violated, then after this has been corrected. it will now work with
the program that it did not work for.


Do you understand how proof by contradiction works? It seems not. See:
http://zimmer.csufresno.edu/~larryc/...ontradict.html

I found this bit particularly amusing:
"The LoopIfHalts() function depends upon access to the return value of
the WillHalt() function. If every possible access to this value is
completely denied to every other program, then LoopIfHalts() can not
possibly effect the WillHalt() function."

So, in other works, WillHalt is no longer a function that can check
whether a program halts or not, since you've just said you can't get
at the return value!

Tom
Jul 22 '05 #5
Peter Olcott wrote:
www.halting-problem.com


You mean you're planning to sell that page? :-)

That seems to be a bit of a proof by semantic shift. The link you cited
states the theorem specifically refers to functions that return the
result.

Anyway, I still can't see how this refutes the seemingly obvious statement:
If it is possible to write a function that calculates X, then it is
possible to write a function that calculates X and returns X to the caller.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Jul 22 '05 #6
Stewart Gordon wrote:
<snip>
That seems to be a bit of a proof by semantic shift. The link you cited
states the theorem specifically refers to functions that return the
result.

<snip>

What I actually meant to say is: One of the links you cited states the
theorem specifically with respect to functions that return the result.

But still....

And by the way, I've noticed that the term "halting problem" has two
very different definitions, based on the double meaning of "problem":

(a) the challenge itself of finding an algorithm to determine whether an
algorithm will halt
(b) the fact that no such algorithm can exist.

Definition (a) is the one I had always understood, and it took me a
moment to get my head around your using definition (b), only to be
followed by a semantic shift to (a) about 1/5 of the way down.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Jul 22 '05 #7
Perhaps this was actually intended as a joke of some kind.
If not, it's good to keep in mind that the internet, in my
experience, is replete with misinformation.
The NIST definition of the Halting Problem is assumed:
No program can ever be written to determine whether
any arbitrary program will halt

This version of the Halting Problem is supposed to be
analogous to every other version, thus valid refutations
of this version should equally apply (with adaptation)
to all other versions.


Or we could conclude that the NIST definition is flawed or
your interpretation is flawed in some way. Indeed, I believe
the interpretation is flawed as the NIST definition seems
slightly ambiguous to me. Perhaps this phrasing is better

No program can ever be written to determine whether
any and all programs will halt.

Then again this phrasing seems to require an infinite amount
of work (this is the problem with natural language ambiguity)
though it seems to be more inline with the framing of the
halting problem as a question of decidability.

The language

ATM = { <M,w> | M is a Turing Machine and M accepts w }

is undecidable.

The authors misinterpretati on of the halting problem seems to
come into play with his refute of objection (2) we he believes
it is sufficient to show that the proof does not apply to SOME
program. When it fact the opposite is true. The proof only
need to apply to a SINGLE program to be valid since this
single program would then be undecidable and since it is a
member of ATM then ATM is undecidable. In fact, the proof
only need to apply to a SINGLE program on a SINGLE input to
be valid.

The author also assumes that the proof requires the ability
to RUN and then READ the output of any program. This is not
the case. In fact, the proof assumes the ability to SIMULATE
or even ANALYZE in any way a program. Were we only able to
RUN a TM then the proof of the halting problem is even
simpler since it is impossible to even create a "WillHalt"
function. For example

M1 = loops on w1
WillHalt ( M1 , w1 ) = ?

In trying ot run M1 on w1 WillHalt will simply loop and thus
not halt. On the other hand, a simulation of M1 can stop at any
time.

Yet, even with the additional power to simulate or analyze
any and every TM it is impossible to decide language ATM.
Jul 22 '05 #8
"Peter Olcott" <ol****@worldne t.att.net> wrote:
www.halting-problem.com
Please quit your courses immediately and sign up for a course on
elementary logic.

Your argument is akin to this one: "If my computer had no CPU, it
wouldn't work. Therefore my computer doesn't work."
(replace 'my computer' with 'the original proof' and 'no CPU' with
'no return value for WillHalt').

Some other logical flaws in your argument:
Method of this Proof
X = The solution to the Halting Problem
Y = The basis of the original proof
Z = The basis of this proof

Structure of Original Proof---->Y makes X impossible
Structure of This Proof--------->Z makes Y impossible


You have misunderstood the OP (Original Proof). The OP starts with:
X = "bool WillHalt() exists"
where WillHalt and its return value are described on the original
page. It explains (in English) why 'X' is equivalent to the
statement of the halting problem.
You are arguing about "void WillHalt()", which has nothing
to do with the OP.

The OP is actually a "reductio ad absurdum". Its structure is
"if X is possible then Y is possible. But Y is clearly impossible."
Many people have trouble grasping this concept (I have no idea why).

If your proof also shows that Y is impossible then you have
only strengthened the OP! If your proof shows that Y is possible
then you have not added to or detracted from it. In order to attack
the OP, you could do one of the following:
- show that X is not equivalent to the halting problem
- show that "if X is possible then Y is possible" is not correct
- show that "Y is impossible" is not correct

You also seem to be of the opinion that refuting the OP
means that you have proved that there is a solution to the HP.
Far from it. Even if you do refute the OP, then there are dozens
of other non-equivalent proofs of the HP. Even if you go further and
refute all known proofs of the HP, it doesn't make it wrong.
It just means that we don't know whether or not there is a solution.
You would actually have to find a solution, or prove that a solution
exists (a very different matter to finding flaws in non-existence proofs).

Finally, most of the effort in your 'proof' seems to have gone into
showing "if bool WillHalt() exists, then void WillHalt() exists". This
is as obvious as it is irrelevant, because the existence of such a
function does not affect the OP. When you revise your page, you should
concentrate on explaining why you think such a function affects the HP
or the OP, and perhaps provide your proof as a footnote.
Jul 22 '05 #9

"tom_usenet " <to********@hot mail.com> wrote in message news:re******** *************** *********@4ax.c om...
On Wed, 21 Jul 2004 12:04:55 GMT, "Peter Olcott"
<ol****@worldne t.att.net> wrote:
The first link on that page defines the halting problem very clearly: No
program can ever be written to determine whether any arbitrary program will
halt. The key phrase here is "any arbitrary." If you try to refute the
claim by modifying the code, then you cannot claim that your solution works
for an arbitrary program.


It works FOR any arbitrary program. It does not work WITH any
arbitrary program. The original analyzer had to be changed. Now
every program analyzed will result in Halting or Not Halting, as long
as the security of the solution has not been violated. If it has been
violated, then after this has been corrected. it will now work with
the program that it did not work for.


Do you understand how proof by contradiction works? It seems not. See:
http://zimmer.csufresno.edu/~larryc/...ontradict.html

I found this bit particularly amusing:
"The LoopIfHalts() function depends upon access to the return value of
the WillHalt() function. If every possible access to this value is
completely denied to every other program, then LoopIfHalts() can not
possibly effect the WillHalt() function."

So, in other works, WillHalt is no longer a function that can check
whether a program halts or not, since you've just said you can't get
at the return value!

Tom


In case you are unfamiliar, the LoopIfHalts() function is the
counter-example used to prove that the Halting Problem
can not be solved. By making LoopIfHalts() impossible
to construct, the original basis of the halting Problem ceases
to exist.
Jul 22 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

31
1931
by: Peter Olcott | last post by:
The Halting Problem can not be solved within the degree of expressability of a TM. My solution only worked because of its more limited degree of expressability. There is no such thing as a void function in a TM, thus there is no way to make constructing the counter-example program impossible for a TM.
0
8621
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9041
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8928
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8890
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7757
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6538
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5877
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4634
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
3
2013
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.