Would it be better to post the paper on https://arxiv.org/ or speak with your local university mathematics department. These would be far more qualified to assess a proof than HN.
What is also suspicious is 5/8ths of the user's past submissions (all on his own blog) have been deleted. Is this some sort of AI-generated traffic farming / engagement gimmick? I don't randomly delete my past submissions to HN from my WordPress.
In this paper, you don't explain anything about the relationship of the complexity classes P and NP to the phenomena about computability of real numbers that you describe. P and NP are defined in terms of whether a specific kind of machine can perform a task in a number of steps that is polynomial in the size of the instance of the task. You didn't explicitly reference any computational problem known to be in either complexity class, nor did you mention any operation whose number of steps to completion (on any abstract machine or computing formalism) you described.
> An algorithm that computes irrationals can
only compute a finite number of irrationals, up to a linear combination over the rationals.
That's not true. A simple counterexample is an algorithm to compute nth roots. All nth roots whose values are non-integral are irrational, and most of them are not linear combinations of one another.
If you want, you can represent an arbitrary number of integer inputs to an algorithm as a single integer. For example, you can do this using Gödel numbering (2^a * 3^b * 5^c * 7^d... gives a bijection between natural numbers and sequences of natural numbers!). The algorithm can start by extracting the various inputs from the "combined" integer input, and can then use those internally.
So, for example, there is a deterministic algorithm that computes the nth digit of the kth root of m, when given a single integer as input which is the Gödel number encoding k, m, and n. This algorithm can compute arbitrary digits of a countably infinite number of irrational numbers, infinitely many of which are not linear combinations of one another!
I think your argument is basically recreating some arguments about the existence of noncomputable numbers (and nonenumerable sets), but you haven't explained how those phenomena relate to complexity classes.
Arguments about computational complexity are often quite different from arguments about computability, because the basic question for complexity is whether something can be done with specific resource bounds, not whether it can be done at all. Recall that the Turing machine formalism has infinite memory available, and something is computable in that formalism if some Turing machine program computes it in any finite number of steps, no matter how large!
6 comments
[ 3.0 ms ] story [ 9.4 ms ] threadWait, is this some kind of social experiment?
> An algorithm that computes irrationals can only compute a finite number of irrationals, up to a linear combination over the rationals.
That's not true. A simple counterexample is an algorithm to compute nth roots. All nth roots whose values are non-integral are irrational, and most of them are not linear combinations of one another.
If you want, you can represent an arbitrary number of integer inputs to an algorithm as a single integer. For example, you can do this using Gödel numbering (2^a * 3^b * 5^c * 7^d... gives a bijection between natural numbers and sequences of natural numbers!). The algorithm can start by extracting the various inputs from the "combined" integer input, and can then use those internally.
So, for example, there is a deterministic algorithm that computes the nth digit of the kth root of m, when given a single integer as input which is the Gödel number encoding k, m, and n. This algorithm can compute arbitrary digits of a countably infinite number of irrational numbers, infinitely many of which are not linear combinations of one another!
I think your argument is basically recreating some arguments about the existence of noncomputable numbers (and nonenumerable sets), but you haven't explained how those phenomena relate to complexity classes.
Arguments about computational complexity are often quite different from arguments about computability, because the basic question for complexity is whether something can be done with specific resource bounds, not whether it can be done at all. Recall that the Turing machine formalism has infinite memory available, and something is computable in that formalism if some Turing machine program computes it in any finite number of steps, no matter how large!