-7

Background: You think the halting problem is silly. Let's solve it. Your solution? You create a program compiler which will always terminate compiled programs in an arbitrary, finite, determinate amount of time t. If the number of clock cylces/second cannot be counted on the system, then the program exits without doing anything. For the Purposes of this question, the frequency of the system processor can be very large. The program may run other programs, however once the timer expires, so do any spawned programs.

For all intents and purposes, we don't consider the program's state an output. The only output that a program has is explicitly what it outputs. For example, looping forever while printing nothing is the same output as printing nothing and halting.

The question:
Given that the compiler's language IS Turing complete, is the compilation with the time limitation also Turing complete?

I should note that a language is considered Turing complete if:

  • It can solve every problem that another Turing complete language can, OR
  • It can solve every problem that a Turing machine can solve.

The following should not necessarily exclude a program form Turing completeness:

  • The program cannot solve every problem that a Turing machine can solve in the same way.

Further more:

Does this compiler solve the Halting problem for any given program?

There have been accumulated a significant number of downvotes on this question. I'm going to assume that this is because there is a lack of merit to such a premise. Allow me 'up the ante'.

As an example, The Arduino Uno, a very popular programming platform has a feature called watchdog. Watchdog is an interesting feature wherein if a program does not execute in a given number of real clock cycles, then the Microprocessor preforms a hard restart.

If the given language / compiler is Turing complete, then a programmer of the Arduino Uno could reasonably program any problem-solving code with or without the use of the watchdog feature. If the language / compiler is not Turing complete then there are said to be some problems for which can be solved without the watchdog, but cannot be solved with the watchdog.

tuskiomi
  • 103
  • 1
    You can turn any language into this fictional language just by plugging the computer into a timer. You can’t solve the halting problem just by forcing a halt. – candied_orange Dec 27 '20 at 22:32
  • @candied_orange well why not? It certainly seems as if I can tell if any program will halt now. The answer? Yes. It will. – tuskiomi Dec 27 '20 at 22:33
  • 4
    see Allen Tunings proofs of the halting problem. It isn’t an issue of needing a better language. – candied_orange Dec 27 '20 at 22:36
  • proof – candied_orange Dec 27 '20 at 22:38
  • @candied_orange Firstly, it seems as if his proof does not take into account Godel's incompleteness theorem. We're talking about finite hardware. Secondly, the proof seems to use a program which never halts as part of the proof. Doesn't this seem to change the validity given the above language? – tuskiomi Dec 27 '20 at 22:39
  • 1
    no. It’s a proof by contradiction. – candied_orange Dec 27 '20 at 22:40
  • @candied_orange Does this mean that Turing completeness relies on Circular logic as part of it's proof, then? The Halt function as you posted would not be possible with said language. However, not halting is also not an output. Looping forever does not indicate that any problem has been solved. Printing nothing, or returning nothing may be a valid output, and for most programs this is the same as looping forever. – tuskiomi Dec 27 '20 at 22:49
  • @tuskiomi Sounds like you might be interested in Chaitin's constant – πάντα ῥεῖ Dec 27 '20 at 23:01
  • @πάνταῥεῖ Yes, very. – tuskiomi Dec 27 '20 at 23:01
  • 1
    @tuskiomi The problem with it is though that the constan's calculation definitely is an NP problem itself, so in practice it's of little use. But for prooving something specific, it's great. – πάντα ῥεῖ Dec 27 '20 at 23:05
  • I'm very curious as to why I'm getting so many downvotes. Is it because there are no apparent merits to answering such a question? – tuskiomi Dec 27 '20 at 23:09
  • 4
    I didn't downvote, but your "create a program compiler which will always terminate compiled programs" suggests that you're misinterpreting what's significant about the halting problem. It's not about the engineering problem of making something stop. It's about showing an example of an abstract problem that's undecidable; other problems that, apparently, have nothing directly to do with halting can be shown to be equivalent to it, and thus to be undecidable as well. See the answers here. – Filip Milovanović Dec 28 '20 at 00:00
  • Let's redefine "the halting problem" to, outputs "1". We can solve the halting problem! PS "the proof seems to use a program which never halts as part of the proof" If there are no programs that never halt, then there's no problem saying whether a program halts, so there's no halting problem. – philipxy Dec 28 '20 at 00:43
  • @philipxySo the answer is yes? – tuskiomi Dec 28 '20 at 00:43
  • Suggest you find out what the definitions of the terms you are using are, then use the terms to mean what they mean, and not what they don't mean. – philipxy Dec 28 '20 at 00:55
  • @FilipMilovanović That's interesting, but on top of other problems with that answer, I see now that The downvotes are likely simply because people don't like the premise of the question, nothing to do with the question itself. It's really unclear if there's a solution to that. – tuskiomi Dec 28 '20 at 01:07
  • "So the answer is yes?" - what philipxy is trying to say is that you framed the question as one about the halting problem (as defined in CS), but then you're not talking about the halting problem (as defined), you're using the same name to talk about about a different problem. – Filip Milovanović Dec 28 '20 at 01:40
  • @FilipMilovanović Well yes, the question is about Turing completeness, I don't see why everyone is getting their collective undies in a bunch over something (yet to find out what) that is minorly related. – tuskiomi Dec 28 '20 at 01:48
  • To solve the halting problem the way you're proposing requires us to first solve the halting problem. Sorry, you can't get there from here. – candied_orange Dec 28 '20 at 02:22
  • @candied_orange ok but can you answer the question? – tuskiomi Dec 28 '20 at 02:24
  • No. Neither computational time limits nor memory space limits are language features of turning completeness. It’s like you asked us what one plus a chicken was. – candied_orange Dec 28 '20 at 05:02
  • @candied_orange You say No, but it sounds to me like you're affirming it's completeness. Are you saying that it isn't Turing complete, or that you are unable toanswer the question? – tuskiomi Dec 28 '20 at 05:24
  • Can your question be rephrased like this: (1) suppose there's a feature that terminates every program after t seconds; Clarification needed: is this an external mechanism, or is this somehow achieved by instructions that the compiler outputs (target language)? (2) The output of the produced program (in the target language) is whatever is printed out by the time it is terminated (forcefully or otherwise). (3) Does this termination mechanism affect Turing completeness of? Target language? Source language? (4) Given any program in the source language, does this somehow solve the HP? – Filip Milovanović Dec 28 '20 at 05:31
  • @FilipMilovanović 1: Doesn't matter. It's terminated magically for all that we care. 2: correct. 3: This is correct. 4: Again, question is not about the Halting problem. It is about Turing Completeness. – tuskiomi Dec 28 '20 at 05:47
  • 1
    I can do better than magic. It's why your keyboard has a Pause/Break button. There is nothing interesting here. This is how they all work. – candied_orange Dec 28 '20 at 06:35
  • Well, that's my point, (1) should matter - if it's ultimately an external mechanism, than it doesn't affect anything regarding (3), because the code doesn't actually have to physically run, it's about what it can do in principle. It doesn't matter if you stop executing at some point, it doesn't matter if you even start. If it's an entirely internal mechanism, then, if I'm not mistaken, the best you can do is to count something, then stop after a certain count. In that case, there are some conceptual problems. 1/2 – Filip Milovanović Dec 28 '20 at 15:59
  • You can interpret that to mean that the source language doesn't do what it says it does. Or you can treat it as a modified language (termination changes its semantics) and say it's not Turing complete. On the other hand, Turing completeness of the target language itself is not affected in the abstract, it's just that the compiler can only generate a certain restricted subset of programs in the target language. 2/2 – Filip Milovanović Dec 28 '20 at 15:59

1 Answers1

6

Is a language which terminates in a given amount of real-time still Turing complete?

No.

It cannot simulate a Turing machine that does not halt.

Jörg W Mittag
  • 103,514
  • Ah! But remember two of my statements.

    1. "For all intents and purposes, we don't consider the program's state an output. The only output that a program has is explicitly what it outputs. For example, looping forever while printing nothing is the same output as printing nothing and halting."

    2. "It can solve every problem that a Turing machine can solve."

     – tuskiomi Dec 29 '20 at 03:09
  • In essence, yes we can. In this case, it would be done with a program that immediately exits. – tuskiomi Dec 29 '20 at 03:18
  • 1
    How does a program that immediately exits print all prime numbers? – Jörg W Mittag Dec 29 '20 at 07:37
  • That is a really good point. Are there any examples of problems not involving infinite sets that you can think of that apply as well as the one above? – tuskiomi Dec 29 '20 at 18:58
  • 2
    For a universally quantified assertion, a single counterexample is enough to invalidate it, so I don't need to think of any other example. – Jörg W Mittag Dec 31 '20 at 15:39
  • After thinking a bit, printing all prime numbers isn't a solvable problem, as solving implies completion... I'm not sure that the case of printing / computing / messing with any infinite list of numbers is something that needs to be done by a machine to be turing complete. Surely, a machine will need to be able to print the first n primes where n is very large, but not where n is infinity – tuskiomi Sep 20 '21 at 17:40