## 1234portion 4 years ago the Haulting question: say there was a computer program, decide whether the program finishes running or runs forever!?!?!

1. dumbcow

i dunno what program is it running? most programs would finish running but if it was stuck in a loop and had a infinite power source then who knows... :)

2. 1234portion

dumb cow, if you dont mind me asking what are your credentials???

3. dumbcow

haha i have 1000 medals

4. zbay

haha

5. Thomas9

The halting problem is about a program that has as input a different program and gives as output whether or not it stops. Apparently it doesn't exist.

6. 1234portion

um... do you have a formal educational back groud, dumb cow?

7. dumbcow

are you really a student?

8. 1234portion

thomas 9, that was an interesting responce

9. 1234portion

but consider the sketch of proof

10. Owlfred

1234 what type of credentials are you looking for?

11. Thomas9

The proof was something with using the initial program as input, but I forgot most of it.

12. estudier

My OS is supposed to run forever, doesn't though.

13. Thomas9

lol

14. Zarkon

I have a Ph.D. Galactic Domination(see profile). How's that?

15. 1234portion

the proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x: that is, the function h is not computable

16. dumbcow

galactic domination...!!?? interesting...

17. 1234portion

thomas 9

18. estudier

Not algorithmically decidable.

19. Thomas9

yes?

20. 1234portion

h(i,x)={1if program i halts on inputx, 0 otherwise

21. estudier

Not recursive.

22. Zarkon

yes...I looked at many universities, but Planet Doom University had the program that i really wanted. Great profeessors

23. 1234portion

are you serious Zarkon?

24. 1234portion

i have not heard from you thomas 9?

25. myininaya

galactic domination! i want that degree

26. myininaya

sounds hot and spicy

27. Ishaan94

Can I apply for Planet Doom University ?

28. Zarkon

yes...the degree is in high demand

29. 1234portion

estudier what do you think?

30. Zarkon

you can...but the off planet tuition is a killer

31. estudier

32. myininaya

what kindof question is this, 1234?

33. 1234portion

well what about my sketch of proof?

34. Ishaan94
35. estudier

Where is it?

36. Thomas9

the proof he means not the university of doom.

37. 1234portion

i am going to copy and repost my earlier responce

38. 1234portion

the proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x: that is, the function h is not computable

39. estudier

The proof sketch, not PDUni.

1234portion -- I didn't see a sketch of a proof. You stated the problem correctly, however.

41. Zarkon

it is not the university of doom...that place it just a diploma mill. Planet Doom University is where I went

The proof itself, at least in the original form presented by Alan Turing, involves defining what a computer is and describing how it runs a program (the then-named Turing machine is the machine that Turing posited for this). I believe you can also prove the same thing using the lambda calculus.

43. Owlfred

1234 Portion, is this your first day on the site?

44. 1234portion

h(i,x)={1if program i halts on inputx, 0 otherwise here program i refers to the i program in an enumeratio of all the programs of a fixed turing complete model of computation.

45. 1234portion

that was for you e studier

46. 1234portion

47. Owlfred

okay cool, how did you find us?

48. 1234portion

browsing... who are you exactly mr.owl?

49. 1234portion

with the utmost respect of course

50. 1234portion

...

Heh. He's the OpenStudy mascot/moderator in chief.

52. 1234portion

and who are you exactly??

The Chief Software Engineer at OpenStudy.

54. 1234portion

cool

55. 1234portion

maby you can answer my question?

56. estudier

I'm not sure what exactly your question is :) Do you want a full proof for the undecidability of the halting problem?

58. Owlfred

Haha, yeah sorry. I'm a moderator on OpenStudy.

59. 1234portion

well thank you for your input e studier

60. myininaya

i say let the computer program run forever

61. myininaya

lol

62. imranmeah91

lol @ myin

63. myininaya

and let the machines take over

64. Zarkon

65. estudier

Q "decide whether" A algorithmically undecidable.

The question of the halting problem is for the general case. Given an arbitrary program, decide whether the program will end or not. It is impossible to write a program that will answer this question every time. It *is* possible to write a program that will answer this question sometimes.

67. 1234portion

estudier you can try to single out possible values for a total computable function, if you have all the variables and an algorithm in place, cant you???

68. 1234portion

shadow friend that is very intriguing, elaborate!

Not sure what you're asking. Can you give an example?

70. 1234portion

just explain more in detail about you response shadow friend, and like i said to estudieryou can try to single out possible values for a total computable function, if you have all the variables and an algorithm in place, cant you???

71. estudier

A more interesting question is quantifying undecidability, or complexity in general.

72. satellite73

i am not sure my computer can even run as long as this thread

73. 1234portion

e studier do you know of any powerful computer programs that postulate very complex and abstract mathematical information?

74. 1234portion

and if you dont mind me asking what are your credentials ??? estudier?

75. satellite73

satelllite md phd psyd do dsw dch university of the galaxy (online)

76. imranmeah91

how many were bought online

77. satellite73

78. 1234portion

what is up with you satellite73???

79. Zarkon

lol

80. 1234portion

i dont find this funny

81. 1234portion

what ever happened to shadow friend?

82. Zarkon

University of the Galaxy ...oooohhh...very prestigious!!

83. satellite73

yeah we used to kick your butts in lacrosse too !

84. Zarkon

yeah...we suck. :(

85. satellite73

girls team did anyway

All right, all right, stay on topic. If you want to talk about the University of the Galaxy, go do it in chat.

87. satellite73

was there a topic or just a credential check?

Heh. Ignore the credential check ;) The topic at hand is the halting problem.

As for my response, I'm just saying that the question of the halting problem is for the general case of any program. You can write a program that recognizes common patterns of programs that halt or don't. You can also decide the halting problem if you're not talking about a general purpose (or Turing-complete) programming language.

90. 1234portion

i understand shadowfriend, however i like to know people educational back ground so i know how capable they are in math, but with that been said, why arent satellit73 talking about my problem, he or she i talking about some space university!

91. 1234portion

it makes no sense !

92. estudier

We judge here by deeds not words...

93. 1234portion

come again e studier???

94. 1234portion

where did that come from?

95. estudier

That is my response to your persistent credential checks, has anyone asked for yours?

96. 1234portion

we should not judge period, who are we to do so?

97. 1234portion

you said we judge by deeds

98. estudier

Correct, then the credential checks serve no useful purpose...

Credentials are de-emphasized on OpenStudy in favor of the community's esteem. Those who want to share them post their school and additional information in their profile.

100. 1234portion

keep in mind i am not being disrespectful, i alway say " if you dont mind me asking, what are your credentals" keep in mind i say " if you dont mind" in a case were people do mind they just dont have to answer!

101. 1234portion

no pressure

102. estudier

Well, doubtless u noticed that people didn't respond..?

I think this particular discussion has run its course.

104. 1234portion

i can see now, sorry for hurting "the communities esteem"

105. 1234portion

back to my question

It's all good :)

107. 1234portion

estudier you seem to be just about the most knowledgeable person here

108. 1234portion

no offence intended to anyone

109. 1234portion

110. estudier

I know a little, so do others, together we know a lot...

111. 1234portion

anyone else want to give it a shot?

112. 1234portion

to my question!

113. zbay

Is this just a theory based question? are you trying to disprove, or prove that this type of program works?

You may also want to try asking in the computer science group at http://openstudy.com/groups/computer+science . Might get some interesting answers there (though not necessarily as fast as here).

115. 1234portion

thank shadowfriend, and to answer your question z bay, i want to see some ones approach on an algorithm or thought analyses, that is also why i am interested in credentials!

116. 1234portion

ok

117. 1234portion

...

118. 1234portion

thanks for you help...i guess?

119. zbay

if you made a program that tested every x value of a function that goes to infinity you would have a never ending program

120. 1234portion

interesting, how did you conclude that zbay?

Unless you developed a computer that could execute infinite operations in finite time, pretty much by definition it wouldn't end.

122. 1234portion

the difficulty with the halting problem lies in the requirement that the decision procedure must work for all programs and inputs.

123. 1234portion

124. 1234portion

?

125. 1234portion

any one?

126. zbay

whats the finance question?

127. 1234portion

ok

128. 1234portion

not to annoy anyone, but zbay would it be too mucn to ask for credentials pertaining to finance??

129. 1234portion

i want to know if you can answer a few accounting questions

130. zbay

i took accounting 1 and didn't like it but i will see if i can remember any of it

131. 1234portion

cool, and thank you very much by the way, ok here it goes!

132. 1234portion

how can one apply the accounting equation effectively towards a government agency's finances?

133. 1234portion

z bay?

134. 1234portion

i only know how to apply the accounting equation to a business entity

135. zbay

you got me

136. 1234portion

oh its ok

137. 1234portion

i like that you tried

138. 1234portion

but i thought there was a finance part to this website, how do i get there?

139. zbay

you can use a basic credit debit system depending on the sizze of the agency would determine the complexity of your accounting system you would have to have all thing equal and you should be good

140. zbay

if you hit the home button at the top you can go to the other groups

141. 1234portion

cool, however unlike a business entity, a gov agency does not receive revenue from a service, so in that case how do you then account for revenue for a gov agency?

142. zbay

well while a gov agency isn't a money making operation they still get funding by other gov agencys so this funding still needs to be accounted for. this would only change the name of the account it wouldn't change the basic process of the accounting process

143. 1234portion

oh!!!!

144. 1234portion

does that also mean gov agencies can not result in a net loss?

145. zbay

in theory you can't spend more money than you have but this doesn't apply to the goverment seeing as they can print more. so while i wouldn't call it a net loss we would call it a deficit.

146. 1234portion

makes scense

147. 1234portion

i think i am well equipped with knowledge from accounting, even thoughits from a business perspective, can i use that same knowledge to effectively do the accounting for a gov agency?

148. 1234portion

???

149. zbay

Yea you can use the accounting process for the gov but your going to have a few problems. they spend lots of money and employ lots of people so your numbers are goign to be huge and collecting the data needed to account for all the money spent is going to be a pain also.

150. 1234portion

ok thank you very much for your insight i must leave no bye, and again thanks!