-3
$\begingroup$

I'm interested in this functions

\begin{align*} g(m) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine $m$ loops on $m$} \\ \text{undefined} & \text{otherwise} \\ \end{cases} \end{align*}

\begin{align*} f(m,n) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine $m$ loops on $n$} \\ \text{undefined} & \text{otherwise} \\ \end{cases} \end{align*}

and the halting problem \begin{align*} h(m,n) &= \begin{cases} \text{0} & \text{if turing machine $m$ loops on $n$} \\ \text{1} & \text{otherwise} \\ \end{cases} \end{align*}

it seems to me that if we have a special unsound solution to the halting problem $h'(m,n)$ we can compute them as follows

\begin{align*} g(m) &= \begin{cases} \text{halt} & \text{if $h'(m,m)=0$} \\ \text{loop} & \text{otherwise} \\ \end{cases} \end{align*}

\begin{align*} f(m,n) &= \begin{cases} \text{halt} & \text{if $h'(m,n)=0$} \\ \text{loop} & \text{otherwise} \\ \end{cases} \end{align*}

whenever $h'(m,n)$ is wrong $h(m,n)=1$ and $m\equiv g$

can you verify that this is true and do you know how we can find $h'(m,n)$? thanks

$\endgroup$
21
  • 1
    $\begingroup$ I'm afraid I don't understand the meaning of this notation precisely enough. $\endgroup$
    – user253751
    Jan 9 at 13:25
  • $\begingroup$ @user253751 I don't know how to make it more clear, what is confusing? $\endgroup$
    – raoof
    Jan 9 at 13:36
  • $\begingroup$ what is the definition of "defined" and "undefined" and "halt" and "loop"? are they just arbitrary names for values (the way we might say "colour(eyeballs) = blue")? because it seems they are not just normal values but I think you are trying to say something special about the function itself (not just that it "returns" the word "defined" or "undefined") $\endgroup$
    – user253751
    Jan 9 at 13:39
  • $\begingroup$ @user253751 "defined" means the function has a value "undefined" mean the function does not have any value, "halt" means the turing machine halts "loop" means the turing machine does not halt. because I am only interested to know whether the function is defined or not, a turing machine that halts whenever the function is defined and loops whenever the function is undefined computes my desired functions. so if I have the special $h'(m,n)$ I can compute my desired functions $\endgroup$
    – raoof
    Jan 9 at 13:46
  • $\begingroup$ and what is a special unsound solution to the halting problem? I don't see that it's specified what h' actually is $\endgroup$
    – user253751
    Jan 9 at 13:48

1 Answer 1

8
$\begingroup$

I see a repeated pattern here, and I'm unsure how to help. I believe the question is meaningless, so instead of trying to answer an ill-defined question that I don't think can be answered, I'm going to instead try to see if I can offer something to help you achieve better understanding of the topic more broadly. I see that you have repeatedly asked questions on a similar theme, and I'm struggling to identify a single conceptual misunderstanding that I think would help to clear up, so instead I'm going to share a broad range of reactions to this question and your previous questions, in hopes that something is of use to you.

To me, I can't make meaningful sense of those questions. To me, this seems to suggest a lack of a fundamental understanding about the concepts. Yet I am not sure how to help you understand better. It seems like many people have tried, but the ways that we have tried have not been successful, and I am not sure what to say that might help you.

I wonder if it's possible that part of the problem is that you may be starting from some premises and hoping for someone to give you a specific answer, e.g., confirm that your beliefs are accurate, and those premises seem faulty to many of us here.

I suspect that another part of the problem is that you are using non-standard notation and terminology that does not match the ways of communicating about this subject that are accepted in the field. At a surface level, your notation and terminology seems tantalizingly like there might be some meaning there. It has all the surface elements: it defines functions, it uses LaTeX, it typesets variables in italics, it correctly recognizes the concept that a Turing machine can compute a function, it recognizes that variables should be defined before they are first used, it has the structure of providing motivation for the questions you are asking. But when I try to read deeply, I just can't make sense of your writing. This seems to be a pervasive problem across many of your questions. I am not sure how to help when I cannot understand where you are coming from.

It's very hard to get answers to complex technical questions if you won't use the standard, accepted terminology. If you won't use standard, accepted terminology, you force readers to try to learn your terminology or your framework for thinking about the topic, which requires lots of extra effort from readers, so many people will just skip over it. And it requires you to precisely define your notation and terminology, which to date seems like it has been a barrier and has not happened successfully in many of your questions. Non-standard terminology or notation risks having built in some faulty premises that might be hard to diagnose or debug. And finally, even if someone answered you, it is unlikely that such answers would be useful to anyone else in the future, because it's unlikely anyone else will use the same non-standard terminology and notation as you do. Part of our mission is to build up an archive of knowledge that will be useful to others in the future.

So I strongly encourage you to first learn and then use standard notation and terminology. I get the impression you may be struggling to do that. That makes me suspect that your time would probably be better spent studying computability theory from a textbook and working through definitions and proofs and exercises there, and asking about specific exercises you are struggling with, rather than asking these particular questions about your ideas about how to approach the halting problem. I wonder if you're jumping straight to the juicy topic of the halting problem without first working through the foundations. Ultra-marathon runners first have to practice running a few miles at a time, and running marathons, before they can take on an ultra-marathon.

On top of that, the halting problem is one of those problems that seem to attract amateurs who think they have found some insight that everyone else in the field has missed, and if everyone else would just listen to their unique insight, they could correct the widespread misunderstanding that has somehow fooled everyone else. A number of us have had experiences of this sort before, where engaging with these folks was a waste of time for everyone before, and have become weary and wary of doing so again in the future. So people come into this area with some built-in wariness or skepticism. And here you come with a series of questions that seems like it might be fitting that pattern. So you are in a particularly difficult territory.

To me, the notation and definitions in your question make no sense. For instance:

  • You can't define a function $g$ in terms of $g$. That's not a meaningful mathematical definition of a function. It's like me trying to define a function by saying that $f(x)$ is one less than $f(x)+1$. That doesn't uniquely specify a function.

  • There seems to be a misunderstanding about the difference between a partial function vs a function. Normally, we don't consider "defined" or "undefined" to be outputs of a function.

  • I'm not entirely sure what you mean by "loops on". If you mean "enters an infinite loop", what counts as an infinite loop? I'm concerned that $h$ might not correspond to the halting problem. The halting problem is concerned with whether a halting problem halts or not, not whether it "loops". Depending on your definition of "loops", it might be possible for a program to neither loop nor halt. If your definition of "loops" is "doesn't halt", then rather than talking about "loops", you should use standard terminology.

  • I don't know what "special unsound solution to the halting problem" means.

  • I don't know what "we can compute them" means (it is not clear what "them" refers to).

  • There seems to be a failure to distinguish between functions vs algorithms/Turing machines. There also seems to be some inconsistency on whether $g$ is a partial function that is defined or undefined on some inputs, vs whether it is a Turing machine that halts or doesn't halt on some input.

  • It's not clear what are the conditions for $h'(m,n)$ to be "wrong".

  • It is not clear what the notation $\equiv$ is supposed to represent.

The problems are pervasive enough that I don't think they can be addressed by a simple edit to fix one or two of them. Instead, I have to call into question the approach you are taking. Perhaps what would help you most is more time studying mathematics, so that you have the formal underpinnings relied upon in computability theory? Perhaps your time will be better spent by learning some other subject without trying to resolve your questions about the halting problem?

My advice is that asking questions of this sort is not working: it's not benefiting our mission of building an archive of knowledge, and from where I sit I don't have confidence that it is helping you understand computability theory. So instead of continuing to ask questions about the halting problem (especially your conceptualization of the halting problem), I would suggest that you try to find some other way to learn about the subject: maybe study from a textbook, maybe ask questions about some other subject entirely, maybe study discrete mathematics and mathematical proofs so you have the foundations needed to succeed in this subject. But at least, I don't recommend continuing along the path you've been following so far, as that path seems to be going nowhere.

$\endgroup$
5
  • $\begingroup$ thank you for your long comment I appreciate your effort to help me, I'm sure there are a lot of thing to learn and improve on. maybe I didn't understand the mission of this website, in any case you are free to delete my questions $\endgroup$
    – raoof
    Jan 10 at 4:34
  • $\begingroup$ @raoof, thank you for your kind words. I realize that I'm making a lot of inferences and reading a lot into your questions, and it is possible I am totally off-base, so I hope you will take my ideas and thoughts with a large grain of salt, and decide for yourself whether they you think they are applicable or not. $\endgroup$
    – D.W.
    Jan 10 at 4:52
  • $\begingroup$ @raoof maybe you can start by figuring out what this "defined and undefined function" stuff means to you. It is acceptable to make up your own mathematics - as long as you can explain what it means so everyone else can follow along. $\endgroup$
    – user253751
    Jan 10 at 8:53
  • $\begingroup$ @raoof I appreciate that the history of mathematics did start off kind of the way you're doing it, but then some mathematicians did think hard about it and came up with precise definitions. For example, a function can be defined as a (usually infinite) set of pairs (x,y), where each x only appears in 1 pair. We say that f(a)=b if (a,b) is in the set. We say that f(a) is undefined if there isn't an (a,anything) in the set and then the function is called partial. $\endgroup$
    – user253751
    Jan 10 at 8:55
  • $\begingroup$ @raoof if that's what undefined meant to you, then I don't see why you'd use defined and undefined instead of just using 1 and 0. So clearly your meaning of undefined isn't the usual meaning and you will have to explain to use what it means. Possibly your meaning of function is also not the usual one especially because functions don't halt or loop. Then you will have to explain that too. And I suggest not calling them functions if they are substantially different from the usual functions (if they are similar it may be okay to call them the same) $\endgroup$
    – user253751
    Jan 10 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.