Random Access Machines with only addition, multiplication, equality

The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they

  1. cannot be simulated by Turing machines in polynomial time
  2. can solve PSPACE-complete problems in polynomial time

However, all of the references I can find on this topic (Simon 1974, Schonhage 1979) also involve boolean operations, integer division, etc.

Do there exist any results for the “reasonableness” of RAMs that only have addition, multiplication, and equality? In other words, which do not have boolean operations, truncated integer division, truncated subtraction, etc?

One would think that such RAMs are still quite “unreasonable.” The main red flag is that they enable the generation of exponentially large integers in linear time, and due to the convolution-ish effects of multiplication, this can get particularly complex. However, I cannot actually find any results showing that this allows for any sort of “unreasonable” result (exponential speedup of Turing machine, unreasonable relationship to PSPACE, etc).

Does the literature have any results on this topic?

Alternate notation for natural numbers and their addition?

The conventional way of expressing natural numbers uses base 10 notation which according to https://matheducators.stackexchange.com/questions/4367/how-to-teach-binary-numbers-to-5th-graders, some people don’t really fully understand how works. Not only that but the notation 2 + 2 + 2 is ambiguous. It could mean (2 + 2) + 2 or 2 + (2 + 2). I know that since addition is associative, all ways of bracketing any addition expression will always give the same answer but that doesn’t change the fact that the expression still has 2 different meanings. Some people refuse to take for granted that both meaning give the same answer just because people sometimes write it without brackets. To add to the extra confusion, we write 2 + 2 and not (2 + 2) and be like “How can I figure out what 2 + (2 + 2) means when I don’t even know what (2 + 2) means?”

The expression 2 + 2 $ \times$ 2 on the other hand can have a different meaning depending on the interpretation unless you use PEDMAS to decide that it can only mean one of those meanings. To make matters worse, some people may get confused by the type of calculator that I think treats all expressions as meaning the left associative expression and rely on its answer being the correct answer using the PEDMAS rule when it’s actually not. I think that because of many confusions similar to those ones, some mathematicians have a demand for formalization and understanding why statements are true. Some mathematicians might insist on having a simple to describe unambiguous notation for natural numbers and all addition expressions of them.

I have an idea for on that I’m wondering if is good. Let 0 denote the natural number 0 and $ S$ denote the successor operation. Now we define the notation for 0 to be $ 0$ , the notation for 1 to be $ S0$ , the notation for 2 to be $ SS0$ and so on. Next to express a sum of 2 natural numbers, we write + followed by the notations for each natural number so 2 + 2 can be represented as $ +SS0SS0$ . For any 2 notations you already constructed, we can also denote their sum as + followed by the notation for the first expression and then the notation for the second expression so (2 + 2) + 2 can be denoted $ ++SS0SS0SS0$ and 2 + (2 + 2) can be denoted $ +SS0+SS0SS0$ . Furthermore, it can be shown that no string of the characters +, $ S$ , and 0 has more than one meaning. Not only that but it can also be shown that given any meaningful expression, sticking more characters onto the end will never give you a meaningful expression. Also when ever you start with the empty string and keep sticking another character onto the end, there’s a nice simple way to compute whether or not you have yet completed a meaningful expression.

Field addition page no longer works after activating my custom field module

I still need your help to solve a problem.

I’m trying to create a custom field, but I can’t. Indeed I have created my module, but when I activate it, the field addition page no longer works. However, I believe I have followed all the instructions in the documentation. My debugger sends me back an error, but despite that when I double-check, I can’t understand why. Please help me out.

The name of my module is called TDL. I want to use it to display the reading time of the articles. These are my files:


<?php    namespace Drupal\tdl\Plugin\Field\FieldType;    use Drupal\Core\Field\Annotation\FieldType;   use Drupal\Core\Field\FieldItemBase;    /**  * Plugin implementation of the 'tdl' field type.  *  * @FieldType(  *   id = "tdl",  *   label = @Translation("Tdl"),  *   description = @Translation("Show time it takes to read article."),  *   default_widget = "tdl_field_widget",  *   default_formatter = "tdl_field_formatter",  * )  */  class TdlItem extends FieldItemBase {   /**  * {@inheritdoc}  */   public static function schema(FieldStorageDefinitionInterface   $  field_definition) {  return array( // columns contains the values that the field will store 'columns' => array(   // List the values that the field will save. This   // field will only save a single value, 'value'   'temps' => array(     'type' => 'vachar',     'size' => '23',     'not null' => TRUE,   ), ), ); }  /** * {@inheritdoc} */ public function isEmpty() { $  value = $  this->get('temps')->getValue(); return $  value === NULL || $  value === ''; }  /** * {@inheritdoc} */ static $  propertyDefinitions;  /** * {@inheritdoc} */ public function getPropertyDefinitions() { if (!isset(static::$  propertyDefinitions)) {   static::$  propertyDefinitions['temps'] = array(     'type' => 'string',     'label' => t('Tdl'),   ); } return static::$  propertyDefinitions; } } 


<?php  namespace Drupal\tdl\Plugin\Field\FieldWidget;  use Drupal\Core\Field\Annotation\FieldWidget; use Drupal\Core\Field\WidgetBase;  /**  * Plugin implementation of the 'tdl' widget.  *  * @FieldWidget(  *   id = "tdl_field_widget",  *   label = @Translation("tdl widget"),  *   field_types = {  *     "tdl_field",  *     "string"  *   }  * )  */ class TdlFieldWidget extends WidgetBase {    /**    * {@inheritdoc}    */ public function formElement(FieldItemListInterface $  items, $  delta,  array $  element, array &$  form, FormStateInterface $  form_state) {     $  element ['temps'] = array (      '#title' => t('TDL'),      '#type' => 'textfield'      '#default_value' => isset($  items[$  delta]->temps) ? $  items[$  delta]->temps : NULL, );       return $  element; }  } 


<?php  namespace Drupal\tdl\Plugin\Field\FieldFormatter;  use Drupal\Core\Field\Annotation\FieldFormatter; use Drupal\Core\Field\FormatterBase;  /**  * Plugin implementation of the 'tdl' formatter.  *  * @FieldFormatter(  *   id = "tdl_field_formatter",  *   label = @Translation("tdl text"),  *   field_types = {  *     "tdl_field"  *   }  * )  */ class TdlFieldFormatter extends FormatterBase { } 

And here is the error returned by php

enter image description here Thank you to help me.

Code outputs capital “D” if input is single 1 or 0 in addition to desired output

Tasked with writing a small program for an intro programming course where “#”s are output in the terminal depending on the integers input, executed when EOF character is input. It looks terrible but it works fine except when a single 1 or 0 is input, then a “D” is output immediately after desired output, and I have no idea why or how it could be possible.

I’ve tried wiggling around in the array used to store input for execution and there are no “D”s in there. There are no “D”s anywhere. It doesn’t happen with any other inputs so far.

int main() {     int n = 0;     int index = 0;     int field[2000] = {};     int length = 0;     while (1)     {         int check = scanf("%d", &n);         if (check == EOF)         {                 break;         }         field[index] = n;         index += 1;         length += 1;     }     for (int i = 0; i < length ; i++)     {         if (field[i] == 0)         {             printf(" ");         }         else         {             for(int j = 0; j < field[i]; j++)             {                 printf("#");             }         }         printf("\n");     }     return 0; } 

I expected a single “#” to be output or a space, no other characters under any circumstances.

Addition of evidence for a fiance visa [on hold]

When we made the visa application we could not submit an English test. This was because we live on north Cyprus and the tests are held only once every six months. We explained this in the visa and offered alternatives such as a Skype interview or a further interview in Nicosia. My partner has now taken and passed the test and we want to advise UK visa of this. The application is still pending. Is this possible and how do we do it. Thank you.

How to execute an HTTP call in addition to RewriteRule (mod_rewrite) in apache?

I have an apache server which redirects URLs to a different one based on some conditions.

I would like to “intercept” this, make a call to an API server, and then continue with the redirect.

So it would somewhat look like this:

RewriteRule ^(.)$ {make API call with $ 1 as a param} RewriteRule ^(.)$ newhost.com/$ 1 [R,L]

I know the above doesn’t work because perhaps RewriteRule isn’t meant for this.

How would I go about accomplish this? I looked in to cgi scripts, but it looks like they need to be called explicitly with a certain URL pattern.

My requirement is no matter what, make an intermediate API call with whatever URL was originally requested, then do a redirect to another URL.

Addition of Strings [in JS]

The task is taken from leetcode

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.


  • The length of both num1 and num2 is < 5100.

  • Both num1 and num2 contains only digits 0-9.

  • Both num1 and num2 does not contain any leading zero.

  • You must not use any built-in BigInteger library or convert the inputs to integer directly.

My solution 1

/**  * @param {string} num1  * @param {string} num2  * @return {string}  */ var addStrings = function(num1, num2) {   let result = '';   let carry = 0;   const LEN1 = num1.length - 1;   const LEN2 =  num2.length - 1;   for (let i = 0, L = Math.max(LEN1, LEN2); i <= L; i++ ) {     const numb1 = num1[LEN1 - i] ? num1[LEN1 - i] | 0 : 0;     const numb2 = num2[LEN2 - i] ? num2[LEN2 - i] | 0 : 0;      const tmp = numb1 + numb2 + carry;     carry = tmp > 9 ? 1 : 0;     result = `$  {tmp % 10}$  {result}`;   }   return carry > 0 ? 1 + result : result; }; 

My solution 2

/**  * @param {string} num1  * @param {string} num2  * @return {string}  */ var addStrings = function(num1, num2) {   let result = '';   let carry = i = 0;   const LEN1 = num1.length - 1;   const LEN2 =  num2.length - 1;    while(num1[LEN1 - i] || num2[LEN2 - i]) {     const numb1 = num1[LEN1 - i] ? num1[LEN1 - i] | 0 : 0;     const numb2 = num2[LEN2 - i] ? num2[LEN2 - i] | 0 : 0;     const tmp = numb1 + numb2 + carry;     carry = tmp > 9;     result = tmp % 10 + result;     i++;   }   return carry > 0 ? 1 + result : result; }; 

Linear time addition of binary numerals using only primitive recursion and case analysis

Given binary numerals encoded like (in Haskell for example):

data Bin = Z | T Bin | TI Bin 

With Z being 0, T n being 2 * n and TI n being 2 * n + 1. We can read TI as 1 and T as 0 to read a reversed binary number. Now we can encode any (natural) number using log2 space, for example:

TI (T (TI Z)) == 5 (read 101) T (TI (TI Z)) == 6 (read 011) 

To implement operations on this data type we are only allowed to use case analysis and primitive recursion:

rec :: Bin -> t -> (Bin -> t -> t) -> (Bin -> t -> t) -> t rec Z cz ct cti = cz rec (T n) cz ct cti = ct n (rec n cz ct cti) rec (TI n) cz ct cti = cti n (rec n cz ct cti) 

We can implement +1 as:

inc :: Bin -> Bin inc n = rec n Z (\n _ -> TI n) (\_ r -> T r) 

We can then implement addition as (by building up a function that calls inc n times):

add :: Bin -> Bin -> Bin add n = rec n id (\_ r -> r . r) (\_ r -> inc . (r . r)) 

This is really inefficient though, is there a more efficient algorithm for addition on binary numerals using only primitive recursion? If not on this encoding, maybe another encoding?

Using general recursion we can do something like:

add :: Bin -> Bin -> Bin add Z m = m add n Z = n add (T n) (T m) = T (add n m) add (T n) (TI m) = TI (add n m) add (TI n) (T m) = TI (add n m) add (TI n) (TI m) = inc (TI (add n m)) 

Which is much better. But I don’t see a way to implement this algorithm using primitive recursion only.