<figure><img src="image_1.png" /></figure>

HAL
open science

# On an Abstract Hypothetical Computational Object

Asad Khaliq

► To cite this version:

Asad Khaliq. On an Abstract Hypothetical Computational Object. 2023. hal-04009974v2

HAL Id: hal-04009974

https://hal.science/hal-04009974v2

Preprint submitted on 1 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
<figure><img src="image_1.png" /></figure>

HAL
open science

# On an Abstract Hypothetical Computational Object
## (Paper Withdrawn)

Asad Khaliq

<figure><img src="image_2.png" /></figure>

► To cite this version:

Asad Khaliq. On an Abstract Hypothetical Computational Object (Paper Withdrawn). 2024. hal-04009974v3

HAL Id: hal-04009974

https://hal.science/hal-04009974v3

Preprint submitted on 8 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On an Abstract Hypothetical Computational Object

Asad Khaliq

E-mail address:asadmalik@giki.edu.pk

Faculty of Electrical Engineering,

GIK Institute of Engineering Sciences and Technology

**Abstract:** Oracle is an abstract hypothetical computational object that can solve decision, function, or even a halting problem in single step. Oracle Turing machines have access to oracles through additional oracle tape. Oracle Turing Machines are hypothetical computation models, but they have been quite useful in advancement of computability and complexity theory. Oracle Turing Machines have been frequently used in separation and classification of languages. Separation between some languages through oracle Turing machines is not possible because of relativization barriers. This paper presents another hypothetical computational object. The aim to develop this new hypothetical computational object is to replace oracle with the new hypothetical computational object, and then explore the possibility to overcome the relativization barriers.

**Key Words.** Oracle, Turing Machine, A-expression, Zarray, Zahem

## 1. Oracle

The idea of oracle in computability was introduced by Alan Turing in his PhD thesis in 1939 [1], and then it was extended into Turing reducibility [2,3]. A problem $P$ is Turing reducible to another problem $Q$ (i.e., $P \le_T Q$) if the oracle machine that computes $Q$ can also compute $P$. Turing reduction works for decision as well as function problems. A.R. Meyer and L.J. Stockmeyer, in 1972, defined polynomial hierarchy (PH) using oracle Turing machines [4]. Oracles Turing machines and Cantor's diagonal argument have been very important tools in separation and classification of languages. Separation between complexity classes $P$ and $NP$ is still an open problem, and solution of this problem through oracle Turing machines and diagonal argument is not possible because there exist oracles $A$ and $B$ such that $P^A = NP^A$ and $P^B \neq NP^B$. This contradictory relativization results were present by Baker, Gill, and Solvay in 1975 [5]. Some very fundamental tools and techniques of complexity theory are quite obscure and poorly understood, and consequences of poor understanding are quite evident in the form of long-standing open problems in complexity theory. Objective of this paper is to develop a new hypothetical computational object and then use it with Turing machines, just like oracles in oracle Turing machines.

## 2. A-expression

A hypothetical computational object that is presented in this paper can compute only particular type of mathematical expressions that are defined as A-expressions. The A-expression are categorized into algebraic A-expressions and numeric A-expressions.

### 2.1. Algebraic A- expressions

*Definition of A-expression:*

An algebraic expression $P$ is A-expression if $P$ has only addition and multiplication operations, and $P$ has only natural numbers as its coefficients and variables. Every A-expression is sum of $S$ zarray for some $S \in \mathbb{N}$.

*Definition of Zarray:*

Zarray is basic unit of A-expressions, and it is represented by $S$ for some $S \in \mathbb{N}$.
Every A-expression splits into zarray under two following conditions. Condition I, if $y = 0$ then $(x)_y = 0$. Condition II, if $y \neq 0$ then $(x)_y = x$.

$P, P_1, P_2, P_3, P_4$, and $P_5$ are examples of algebraic A-expressions. In these examples, left subscript specifies the variable, and we use right subscript to count zarray in the A-expression. After replacing multiplications with summations in A-expressions, every A-expression consists of sum of zarray. These A-expressions split into zarray under two conditions that are mentioned in the definition of zarray. The algebraic A-expressions $P, P_1, P_2, P_3, P_4$, and $P_5$ consist of $y, r + 1, 2x, 2_2x, f$ and $2x + _1x_2x$ zarray, respectively. If $\{P, P_1, P_2, P_3, P_4, P_5\} \subseteq$ set of A-expressions, then $\{y, _2x, 2_2x, f, _2x + _1x_2x\} \subseteq \mathbb{N}$.
# On an Abstract Hypothetical Computational Object (Paper Withdrawn)

Asad Khaliq

**Withdrawal Note:** This paper is too abstract to be understood. It would be republished with extended explanations at appropriate time.
$$P = xy$$

$$xy = \sum_{a=1}^{y} (x)_a$$

$$xy = x_1 + x_2 + x_3 + x_4 + \dots + x_y$$

Sum of y number of x is equal to A-expression P. The A-expression P has y number of zarray, i.e., S = y. Similarly, we can split any algebraic A-expression into zarray and count the number of zarray. As stated earlier, right subscripts of variables represent count of zarray in these A-expressions.

$$P_1 = 0r + 7$$

$$0r + 7 = \sum_{a=1}^{r} (0)_a + 7$$

$$0r + 7 = 0_1 + 0_2 + 0_3 + 0_4 + \dots + 0_r + 7_{r+1}$$

$$P_2 = \prod_{n=1}^{2} n x$$

$$1x_2x = \sum_{a=1}^{2^x} (1x)_a$$

$$1x_2x = 1x_1 + 1x_2 + 1x_3 + 1x_4 + \dots + 1x_{2^x}$$

$$P_3 = \prod_{n=1}^{2} n x + \prod_{i=2}^{3} i x$$

$$1x_2x + 2x_3x = \sum_{a=1}^{2^x} (1x)_a + \sum_{b=1}^{2^x} (3x)_b$$

$$1x_2x + 2x_3x = 1x_1 + 1x_2 + 1x_3 + 1x_4 + \dots + 1x_{2^x} + 3x_1 + 3x_2 + 3x_3 + 3x_4 + \dots + 3x_{2^x}$$

$$P_4 = \prod_{n=1}^{m} n x$$

$$1x_2x_3x_4x \dots m x = \sum_{g=1}^{m^x} \left( \dots \sum_{c=1}^{4^x} \left( \sum_{b=1}^{3^x} \left( \sum_{a=1}^{2^x} (1x)_a \right)_b \right)_c \right)_g$$

$$1x_2x_3x_4x \dots m x = 1x_1 + 1x_2 + 1x_3 + 1x_4 + \dots + 1x_f$$

$$f = 2x_3x_4x \dots m x$$

$$P_5 = \sum_{y=1}^{2} \prod_{i=1}^{2} i x y$$

$$1x_2x + 4_1x_2x = \sum_{a=1}^{x_2} (x_1)_a + \sum_{b=1}^{x_2} \left( \sum_{a=1}^{x_1} (4)_a \right)_b$$

$$1x_2x + 4_1x_2x = 1x_1 + 1x_2 + 1x_3 + 1x_4 + \dots + 1x_{2^x} + 4_1 + 4_2 + 4_3 + 4_4 + \dots + 4_{1x_2x}$$

After replacing multiplications with summations, the A-expressions consist of only sum of zarray, and total number of zarray in any A-expression can vary because it depends on the variables selected for expansion and the variable selected for limits. If P = xy is A-expression and x ≠ y then number of zarray in P will be different if y is selected for expansion instead of x.
## 2.2. Numeric A-Expressions

**Definition of A-expression:**

A numeric expression $Q$ is A-expression if $Q$ has only addition and multiplication operations, and if $Q$ has only natural numbers in the expression. Every A-expression is sum of $S$ Zarray for some $S \in \mathbb{N}$.

**Definition of Zarray:**

Zarray is basic unit of A-expressions, and it is represented by $S$ for some $S \in \mathbb{N}$.
Every A-expression splits into zarray under two following conditions. Condition I, if $y = 0$ then $(x)_y = 0$. Condition II, if $y \neq 0$ then $(x)_y = x$.

Numeric A-expressions split into zarray under two conditions that are mentioned in the definition of zarray. $Q, Q_1, Q_2$, and $Q_3$ are examples of numeric A-expression. $Q, Q_1, Q_2$, and $Q_3$ consist of 9, 10, 84, and 36 zarray, respectively. Because $\{Q, Q_1, Q_2, Q_3\} \subseteq$ set of A-expressions therefore $\{9, 10, 84, 36\} \subseteq \mathbb{N}$.

$$Q = 7 \times 9$$

$$\begin{aligned} &= \sum_{a=1}^{9} (7)_a \\ &= 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 \end{aligned}$$

As stated earlier, there are two conditions to split A-expression into zarray. These conditions are explained through splitting A-expression $Q_1$ into zarray. Number of zarray may vary but sum of zarray is equal to $Q_1$.

$$Q_1 = 10 \times 0$$

$$\begin{aligned} 10 \times 0 &= \sum_{c=1}^{10} (0)_c \\ &= 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 \\ 10 \times 0 &= \sum_{d=0}^{10} (10)_d \\ &= 0 \end{aligned}$$

$$Q_2 = \prod_{n=3}^{6} n + \prod_{n=1}^{3} 2n$$

$$\begin{aligned} 3 \times 4 \times 5 \times 6 + 2 \times 4 \times 6 &= \sum_{c=1}^{3} \left( \sum_{b=1}^{4} \left( \sum_{a=1}^{5} (6)_a \right)_b \right)_c + \sum_{e=1}^{6} \left( \sum_{d=1}^{4} (2)_d \right)_e \\ &= 6_1 + 6_2 + 6_3 + \dots + 6_{60} + 2_1 + 2_2 + 2_3 + \dots + 2_{24} \end{aligned}$$

$$\begin{aligned} Q_3 &= \sum_{n=5}^{7} \prod_{m=1}^{2} mn \\ &= 5 \times 2 \times 5 + 6 \times 2 \times 6 + 7 \times 2 \times 7 \\ &= \sum_{d=1}^{5} \left( \sum_{a=1}^{2} (5)_a \right)_d + \sum_{f=1}^{6} \left( \sum_{e=1}^{2} (6)_e \right)_f + \sum_{h=1}^{7} \left( \sum_{g=1}^{2} (7)_g \right)_h \\ &= 5_1 + 5_2 + 5_3 + \dots + 5_{10} + 6_1 + 6_2 + 6_3 + \dots + 6_{12} + 7_1 + 7_2 + 7_3 + \dots + 7_{14} \end{aligned}$$

After replacing multiplications with summation, every A-expression consists of only sum of zarray, and number of zarray may vary because it depends on the integer selected for limits and the integer selected for expansion. In $R = 7 \times 9$, the number of zarray depends on the integer we chose for limits in summation and the integer we chose for expansion; but irrespective of order of these choices, we can split any A-expression into zarray.

## 3. Computation of A-expression

Zahem-Zarray is a hypothetical computational object, and it is represented by $Z_z^k$ for some $k \ge 2$ and $k \in \mathbb{N}$. The $Z_z^k$ splits any A-expression into zarray and then adds $k$ zarry in single step. If $Z_z^k$ splits
A-expression into S zarray then there are three possibilities i.e., $k > S$, $k = S$ or $k < S$. $Z_Z^k$ will compute any A-expression with S zarray in single step if $S \le k$ but it will take more than one step if $S > k$. $Z_Z^2$ will require one step to compute A-expression $2 \times 2$ because $S = 2$, but $Z_Z^2$ will require three step to compute another A-expression $2 \times 2 \times 2$ because $S = 4$. $Z_Z^k$ with $k \ge 4$ will compute $2 \times 2 \times 2$ in single step because $S \le k$. If an A-expression F has S zarray and $S > u > v$ then $Z_Z^u$ will take less number of steps than $Z_Z^v$ to compute F. Pictorial representation of fundamental Zahem-Zarray ($Z_Z^2$) and its generalized form ($Z_Z^k$) is shown in Fig.1.

<figure><img src="image_2.png" /><figcaption>Fig. 1 Fundamental Zahem-Zarray ($Z_Z^2$) and its generalized form ($Z_Z^k$)</figcaption></figure>

If there is an A-expression $G = 100 \times 100 + 0$ and aim is to compute $G$ through $Z_Z^r$ for some $r \in \mathbb{N}$, then $Z_Z^{10}$, $Z_Z^{50}$, and $Z_Z^{101}$ would take 12 steps, 3 steps and 1 step, respectively. All A-expression are function problems, but all A-expression are not subset of FP, i.e., any deterministic polynomial time Turing machine cannot compute every A-expression.

**Zahem-Zarray lemma I**

If there is a problem P in complexity class FP and P is also an A-expression with S zarray, and $S \le m$ then $Z_Z^m$ can compute P in single step.

As stated earlier, there are some A-expressions that are not contained in complexity class FP. Now we describe those A-expressions that are contained in complexity classes that are more powerful than complexity class FP.

**4. Permanent as A-expression**

Immanant of a matrix is generalized notion of determinant and permanent, and it was defined by D.E Littlewod and A.R. Richardson in 1934 [6]. The permanent of an $n \times n$ matrix $M = (m_{ij})$ is defined as

$$ \mathrm{Perm}(M) = \sum_{\sigma \in S_n} \prod_{i=1}^{n} m_{i, \sigma(i)} $$

$S_n$ is symmetric group that is defined over permutation of $n$. If $m_{ij} \in \mathbb{N}$ then $\mathrm{Perm}(M)$ is A-expression. Suppose there is $2 \times 2$ matrix $F$ with $f_{ij} \in \mathbb{N}$

$$ F = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \\ \mathrm{perm}(F) = ad + bc \\ ad + bc = \sum_{g=1}^{d} (a)_g + \sum_{h=1}^{c} (b)_h \\ = a_1 + a_2 + a_3 + \dots + a_d + b_1 + b_2 + b_3 + \dots + b_c $$
$Z_z^k$ can compute permanent of $F$ in single step if $d + c \le k$, but if $d + c > k$ then $Z_z^k$ would require more than one step to compute permanent of $F$ unless we increase the order of zahem (value of $k$). We can combine the concepts of A-expression, $Z_z^k$, and permanent of a matrix in the form of following lemma.

**Zahem-Zarray lemma II**

If there is an $n \times n$ matrix $M = (m_{ij})$ and $m_{ij} \in \mathbb{N}$ then $\text{Perm}(M)$ is A-expression. If A-expression of $\text{Perm}(M)$ has $S$ zarray and $S \le k$ then $Z_z^k$ can compute $\text{Perm}(M)$ in single step.

There exist $k$ such that $Z_z^k$ can compute permanent of any $n \times n$ matrix $M = (m_{ij})$ if $m_{ij} \in \mathbb{N}$. Computation of permanent is very important problem in complexity theory because permanent is $\#P$ complete [7]. Unlike oracle, the internal construction this hypothetical computational object (Zahem-Zarray) is known. In subsequent work, *Zahem-Zarray lemmas* will play important role in derelativization of relativized complexity classes $P$ and $NP$. Relation of $Z_z^k$ with uniform and nonuniform models of computation will be part future work.

**5. Conclusion**

Oracle Turing Machines are hypothetical computational objects because they are based on oracles. Cantor's diagonal argument and oracle Turing Machines have been very important tools for separation and classification of languages, but these tools are ineffective in some cases because they fail to separate some complexity classes due to relativization. This paper presents another hypothetical computational object that is represented by $Z_z^k$ and two lemmas that are based on $Z_z^k$. Lemma I states that there exist $m$ such that $Z_z^m$ can compute some problems from complexity class $FP$ in single step. Lemma II states that there exist $k$ such that $Z_z^k$ can compute permanent of some matrices in single step. In future work, we will establish important results by replacing oracles with $Z_z^k$ in oracle Turing machines.

**References**

[1] Turing, A.M., 1939. Systems of logic based on ordinals (Ph. D. thesis). *Princeton University*, P.8.

[2] Post, E.L., 1944. *Recursively enumerable sets of positive integers and their decision problems*. World Scientific.

[3] Rogers Jr, H., 1987. *Theory of recursive functions and effective computability*. MIT press.

[4] Meyer, A.R. and Stockmeyer, L.J., 1972, October. The equivalence problem for regular expressions with squaring requires exponential space. In *SWAT* (Vol. 72, pp. 125-129).

[5] Baker, T., Gill, J. and Solovay, R., 1975. Relativizations of the $P=?$ NP question. *SIAM Journal on computing*, 4(4), pp.431-442.

[6] Littlewood, D.E. and Richardson, A.R., 1934. Group characters and algebra. *Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character*, 233(721-730), pp.99-141.

[7] Valiant, L.G., 1979. The complexity of computing the permanent. *Theoretical computer science*, 8(2), pp.189-201.