-4

Background: this is a continuation of this question here, further expanding the thought experiment.

In short, you have a magic calculation machine which has the following properties.
The machine is:

  • Fast. The rigid definition is that the processor frequency can be arbitrarily high (though not infinite).
  • Finite. (NEW) Any program that runs on this processor has a fixed, finite input and output size. If the program tries to output more information than it's pre-determined output size, the machine immediately exits. It is not possible to alter these values.
  • Frugal. This means that the output of the machine is strictly the data that is outputted. This means that the state of the machine is not an output, and a program that loops infinitely without printing anything has the same output as a program that exits immediately. Expanding on the finite quality of our machine, this means that both of the previous examples are equivalent to any program which has a pre-determined output size of 0.
  • Fleeting. The processor has a pre-determined time of execution. This time can be arbitrarily high, but not infinite.

The question:

Given that the processor IS Turing complete with only the [fast] quality, is the processor with the other limitations 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 the halting problem occur for any program in this processor?

tuskiomi
  • 103

1 Answers1

2

No.

Here's a simple example: consider a Turing machine which computes the series of prime numbers.

For any arbitrarily large limit you choose for your Tuskiomi Machine, there is a finite series of prime numbers one larger that it cannot compute but a Turing Machine can.

So, you say "Then I just add more resources to my Tuskiomi Machine so that it can compute one more prime number!" But then there is still the problem that your Machine cannot compute two more prime numbers.

So, you say "Then I just add more resources to my Tuskiomi Machine so that it can compute a googol more prime numbers!" But then there is still the problem that your Machine cannot compute a googol plus one more prime numbers.

Does the halting problem occur for any program in this processor?

The Halting Problem says that there cannot be a program H(p, i) which decides whether program p will halt for input i.

Obviously, this problem does not exist for your Tuskiomi Machine, because I can trivially write program H:

def H(p, i):
    return true;

Therefore, the Halting Problem is trivial.

Jörg W Mittag
  • 103,514
  • See the comments on the question for why this is falsidical, also see the Finite requirement that a program know how the upper limit to how much it can output before it runs. – tuskiomi Feb 19 '21 at 05:13
  • Also see the Fast requirement that states that both memory and speed are arbitrarily high. in your example, my magic CPU can calculate any number of primes, so long as the number of primes you want is a real positive integer, or zero. – tuskiomi Feb 19 '21 at 05:32
  • For any arbitrarily large speed you choose for your Tuskiomi Machine, there is a finite series of prime numbers one larger that it cannot compute but a Turing Machine can. So, you say "Then I just make my Tuskiomi Machine faster so that it can compute one more prime number!" But then there is still the problem that your Machine cannot compute two more prime numbers. So, you say "Then make my Tuskiomi Machine faster so that it can compute a googol more prime numbers!" But then there is still the problem that your Machine cannot compute a googol plus one more prime numbers. – Jörg W Mittag Feb 19 '21 at 05:51
  • When I say any number, I mean any number. before you say it, think it, count it, before you started typing this answer, it was, is, and forever will be possible. There is no 'add more memory'. there is enough memory. There is no 'speed up the processor' it has always been fast enough. – tuskiomi Feb 19 '21 at 07:10
  • 3
    When you say any number, I say any number plus one. – Jörg W Mittag Feb 19 '21 at 08:23
  • any number + 1 ∈ any number. – tuskiomi Feb 19 '21 at 15:43
  • It does not matter which constraints you chose for your Tuskiomi Machine. It is completely irrelevant. The Laws of Mathematics guarantee that whatever your arbitrary number is, there still is a bigger one. And there will always be at least one program that a Machine with higher limits than yours can compute, namely the program which prints a string of 0s on the tape that is one longer than the tape of your Tuskiomi Machine. Therefore, by the Laws of Mathematics, it is guaranteed that there always exists a Machine that can compute at least one programyour Tuskiomi Machine cannot. – Jörg W Mittag Feb 19 '21 at 18:06
  • I see what your saying, and I think the issue is that you think that the resources are static, when I wrote the question I meant to say that the resources can be changed arbitrarily between program executions – tuskiomi Feb 19 '21 at 20:58
  • Figuring out the resource requirements of a program is provably undecidable, so you have to pick (or "guess") a number. Then I build a machine that is exactly identical to yours, except its guessing algorithm is "whatever you guessed plus one". By the Laws of Probability Theory, if we play this game often enough, there will be an instance where you guessed exactly one too low, so my machine can execute the program and yours can't. – Jörg W Mittag Feb 19 '21 at 21:08