DEV Community: Parsa VxT

Halting Problem, the undecidable problem for Turing machines...

Parsa VxT — Thu, 29 Jul 2021 14:42:10 +0000

In 1936, the Englishman Mathematician, Alan Turing invented a machine called the Turing machine, Turing machine is a model of computation that's able to manipulate the symbols on a tape as a series of defined rules, the machine header will move over the cells of the tape which can read‌ and write symbols on the cells of the tape based on its given instruction.

With the help of the Turing machine, we are able to solve any computational problems that have the ability to define mathematically.

But wait a second! Did we say any problem? Well, no... there are some undecidable problems like the subject of this article that is the Halting problem and the NP-Hard one!

Halting Problem:

Halting Problem is a decision problem, in summary, that mean we have to answer that by true or false, yes or no.
e.g:

fn is_odd(x: i32) -> bool {
    return x % 2 != 0
}

The halting problem is about determining that if we give a value to a machine, that will halt or will be looping forever, in the following, i will explain it in a straightforward way...

Proof:

as we said our goal is to develop a machine/algorithm that should recognize what happens if we execute an arbitrary program with a specified value, it will halt or will be stuck in an infinite loop.
in this example we will consider there is a willHalt function that will tell us the given program will halt with the given value or not! (this is merely an assumption)
this is somehow a sample code:

const willHalt = (cb, value) => (cb(value) === "Halt" ? true : false);

okay, now we want to create an arbitrary program that will prove that the willHalt program can't exist, by creating a paradox!

there is a program called arbitraryProgram that takes a parameter as input and then executes the willHalt program with its own input value, (if) the willHalt returns true, an infinite loop will be executed, otherwise the Halt value will be returned, and here is another sample code:

function arbitraryProgram(value) {
  if (willHalt(value, value)) {
    while (true) {}
  } else return "Halt";
}

what do you think will happen if we run the arbitraryProgram function with itself as input like this arbitraryProgram(arbitraryProgram)?
infinite recursion...? No! as we said earlier, we will consider that the willHalt function will tell us the correct answer the first time.

take a look at this flowchart:

as you see in flowchart the problem is the arbitraryProgram function, let's check it out...

-> if willHalt function says "true", an infinite loop will be executed, then our program will stuck in an infinite loop! the willHalt answer is wrong!

and in another mode:

-> if willHalt function says "false", the arbitraryProgram will stop by returning a value, and again the answer of willHalt function is wrong...
and this proves us the willHalt function can not exist!

but what if we don't assume that the willHalt function works finely? simple! tjat will contiue running forever until the call stack has reached its maximum limit!
.
.
.
.
.
the halting problem is just one of the undecidable problems, if you are interested in these type of issues, there are other problems such as Entscheidungsproblem that you can research about it.

if this post was helpful, share it with others... tnx.

research resources:
https://www.youtube.com/watch?v=wGLQiHXHWNk
http://people.seas.harvard.edu/~salil/cs121/fall12/lecnotes/TM.pdf
https://www.quora.com/What-is-the-difference-between-Entscheidungsproblem-decision-problem-and-Halting-problem

Implement the bubble sort algorithm using TypeScript

Parsa VxT — Mon, 29 Mar 2021 19:10:47 +0000

without any exaggeration, Let's go to the main topic! we start with a question:

what's bubble sort?

bubble sort is a simple sort algorithm to sort a list by scanning and swapping the values in each step if they are in the wrong place (it depends on sort order [ascending/descending]).

Let's go!

in this scenario, we want to sort an array in ascending order.
as we know, an algorithm consists of several specified properties:

Input: an initial value in a specified structure.
Output: the expected value after processing on Input value.
Finiteness: algorithm must stop working after a specified step.
Definiteness: the operations of each step must be specified.
Effectiveness: the instructions must be simple and without any unnecessary actions.

first of all, to obtain the first requirement (input) we have to construct a function that returns an un-sorted array with random numeric values like the below example:

function genRandomArray(arrLength: number) {
  return [...Array(arrLength)].map(() =>
    Math.floor(Math.random() * (100 * arrLength))
  );
}

okay, now we have a dataset generator so let's explain the algorithm:

in this algorithm we have two pointers, like this:

in each step, each value will be compared with its next value:

if currentValue was bigger than nextValue swap them.
if currentValue was smaller than nextValue pass the step and compare the two next values.
if currentValue was equal to nextValue do nothing and the same as the last case, pass it and compare the two next values.
if pointers reach the end of the list: Repeat the algorithm.

End Of Process: these operations are repeated until all of the numbers are fully sorted (if this not make sense, take a look at the following example).

now come to take a look at implemented code:

function bubbleSort(arr: number[]) {
  const cpyArr = [...arr];
  const { length } = cpyArr;

  const swap = (a: number, b: number): void => {
    cpyArr[a] = cpyArr[a] + cpyArr[b];
    cpyArr[b] = cpyArr[a] - cpyArr[b];
    cpyArr[a] = cpyArr[a] - cpyArr[b];
  };

  for (let x = 0; x < length - 1; x++)
    for (let y = 0; y < length - 1 - x; y++) {
      const [currentIndex, nextIndex] = [y, y + 1];
      if (cpyArr[currentIndex] > cpyArr[nextIndex])
        swap(currentIndex, nextIndex);
    }

  return cpyArr;
}

console.log(bubbleSort(genRandomArray(10)));

a short quotes about swapping from Wikipedia:

In computer programming, the act of swapping two variables refers to mutually exchanging the values of the variables.
Usually, this is done with the data in memory.

HINT: if you want to sort the array in descending order, you merely have to change the Greater than operator to smaller than operator in if condition, it makes the algorithm works reverse!

thanks for reading!

Display ram usage by LEDs using Arduino & Javascript!

Parsa VxT — Tue, 05 Jan 2021 20:41:26 +0000

Hey, today we gonna start an interesting project...
umm, what's it? As you see in the title, displaying the computer RAM occupied using LEDs.

The tools we employ are as follows:

Arduino UNO
Breadboard
Jumper wire (Male to Male)
colored LEDs
nodeJS/Johnny five
any editor! even notepad XD
Arduino IDE (just for load standardFirmata onto the board)

What’s Arduino?

Arduino is a kind of mini-computer that aims to simplify programming for Avr microcontrollers. One of the most significant achievements of this goal, not restricting the users of this device to electrical professionals.
Which means you can implement your ideas so easily. it consists of a circuit board on which there is a programmable microcontroller. this microcontroller receives signals from the connected actuators, which it can evaluate with your saved programming code. Depending on your code, it sends a series of signal to the pins, which then carry out a certain action. This means the Arduino can communicate with the environment with the help of sensors and actuators.

Which framework are we going to use?

We are going to use johnny five! It’s a JavaScript library to write programs and communicate with electronic boards like the Arduino series.

Here We Go!

initially, we have to load standardFirmata/standardFirmataPlus onto the board, so connect your board to the computer and open Arduino IDE, navigate to File > Examples > Firmata > StandardFirmataPlus (or) StandardFirmata then click on upload button.

you may ask yourself, what is the Standard firmata? it's a library to implement firmata protocol for communication with other softwares on the computers.

well, create a project with the following commands:

~$ mkdir progress-bar
~$ yarn init
~$ yarn add johnny-five --save

then implement LEDs row on breadboard and finally connect those to Arduino, as below schematic:

It's time to code!

1- first create 'index.js' file then import johnny five:

const five = require("johnny-five");

2- initialize the board:

const board = new five.Board({
  debug: true,
});

NOTE: you don't need specifying the board port, coz johnny five will detect that automatically.

3- specifying 'pins' and 'LEDs' array to save Led methods:

const pins = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];
const leds = [];

4- set the "connect" event to know when the board is connected.

board.on("connect", () => {
  console.log("board connected!");
});

5- the essential part of our program! "ready" event, that place we have to write our codes to control the board, the callback of the "ready" event will execute when the board is ready to use:

board.on("ready", () => {
  console.log("Board is ready!");
});

6- presently we have to initialize and store LEDs methods in the 'leds' array which those pin stored in the 'pins' array:

pins.forEach((pin) => leds.push(new five.Led(pin)));

7- declaring a method to turn off all of the LEDs:

const ledsOff = () => leds.forEach((led) => led.off());

now we require a function that computes occupied space and returns a number that defines how many led must be turning on, we use the os api to get the RAM capacity and its free space.

8- to obtain this value, we utilize the following process:
~> import 'os';
~> store total RAM space
~> store free ram space
~> store and calculate the amount of space occupied
~> divide all the RAM space between all the pins to get (step x number of pins)
~> Calculate how many LEDs should be turned on, to perform this just need to divide the occupied space between steps!

code:

function calc() {
  const totalRam = os.totalmem();
  const freeRam = os.freemem();
  const usageRam = Math.floor(totalRam - freeRam);
  const steps = Math.floor(totalRam / pins.length);
  const count = Math.floor(usageRam / steps);

  return count;
}

9- define a method for turning on a series of LEDs to show the progress bar:

const showProgress = (n) => {
  if (typeof n !== "number" || n > pins.length)
    throw Error("'n' parameter must be number and less than" + pins.length);

  for (let x = 0; x < n; x++) leds[x].on();
};

hmm, it's almost over, let's complete the last section.
10- define a variable to store the last number of LEDs which those must on plus an interval to refresh the progress bar every 500 milisecond:

let lastStatus = calc();
setInterval(() => {
 if (calc() !== lastStatus) {
   ledsOff();
   lastStatus = calc();
 }
 showProgress(calc());
}, 500);

Yay! our work is over...🎉
all we need to do now is execute the script and see the output.