## Universal Turing Machine algorithm

First, I learned this based on these facts:

1. Turing machine (TM) will be define with 7-tuple Notation, M=<Q,G,b,S,d,q0,F>.
2. Any computation rules that can use to simulate any possible TM is called Turing-Complete.
3. Universal TM (UTM) is TM that is Turing-Complete.

Then, the question begins:

• If we have 7-tuple Notation of any U that is UTM, Is there an algorithm to find initial tape content P that U to simulate any TM T with any I input(s)? If it exists, Does it based on each U or pattern of U? If it does, give me some example(s)? If it does, explain the algorithm?
• Since all possible computations can be done with TM, Is there an algorithm to make TM simulate any algorithm P written in any language? If it exists, give me some example(s)?
• If both questions above exist the algorithm, Why don’t we just make a single UTM U and use it to program itself then do every possible computation?

## Figure out if this is LL(1) grammar

S → ( T )

T → U | U , T

U → x | S

I got these two questions?

(b) Is the grammar LL (1)? (c) Is the language LL (1)?

I don’t know exactly how to figure this out? They say that you should look left recursion in this grammar? But i’cant figure out this thing?

## Vulnerabilities in Airflow

I am by far not a security expert and I would like to use Airflow, but security is blocking the usage due to vulnerable aspects. When I asked the specifics they directed me to the given one The Airflow Celery workers deserialize pickle data that is stored in the message broker—Meaning that if I can get access to the message broker, I can achieve remote code execution inside the workers by a deserialization attack. This vulnerability was assigned CVE-2020-11982.

Originated from this blog. https://snyk.io/blog/message-brokers/

I am really getting the statement from them that Airflow is insecure. But it is the most popular, therefore there must be ways to secure it. Would there be any advise how to proceed?

## Is escaping a concept in CS?

I understand "escaping data" as making an exception when matching data; for example, if a program can’t match data wrapped in single and/or double quotes without an exception, than we make an exception, "escaping" such characters to be matched.

Is escaping a concept in CS?
Is it "part of how any computer would work" or just a technical implementation in human-developed programming languages?

## Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck.

Given a binary tree where each node in the tree can either be selected or unselected, implement a function k_away() which returns the minimum number of nodes that need to be selected so that every node in the tree is at most k nodes away from a selected node.

So, the nodes simply contain a pointer to the left child, a pointer to the right child, and a boolean marking it as selected or not:

struct Node {     Node *left;     Node *right;     bool selected = false; // starts out false }; 

The problem specifies a constraint of having a time complexity of O(n) and an auxiliary space complexity of O(n).

What I’ve thought of so far:

• It seems like there are 2^n potential solutions (if I can choose to either select or not select every node and there are 2 of them), so brute force is a bad idea
• I’ve searched around for similar problems and the closest thing I can find is the Dominating Set problem which seems… impossible to solve at this moment in polynomial time. I doubt this problem was given as an impossible problem.
• Running DFS to get to the leaf nodes, then counting height as recursion unrolls. Every k away, marking the node as selected. This seems to work on small test cases, but does not return the minimum number away.
• Running BFS on the root node to find all nodes k away while using another data structure to mark all visited nodes as ‘covered’, and then recursively running the BFS on each k-away node. This also seems to work on small test cases, but again doesn’t return the minimum number away.

## Are two 8 GB DDR3 (1600) better than two 8 GB DDR3 (1600) + one 4 GB DDR3 (1333)? [closed]

I have an old computer setup which has two 8 GB DDR3 (1600) RAM. I have found another 4 GB DDR3 (1333) RAM and trying to understand whether adding this 4GB RAM with those already mounted 16GB RAM will increase the computer performance or not.

I don’t have much knowledge on computer hardware. If anybody could give me an answer in layman’s term, I would be grateful.

## Algorithm for summation with lowest maximum temporary sum

I’ve got this problem on my last exam, which I struggle to deal with.

Lets say we have array of N integers (it can be float too, but lets say integers for sake of simplicity. We need to sum those numbers, but we can only use operation of summing two adjacent numbers. Goal of algorithm is to sum this sequence, so maximum of sum from this operation will be lowest possible.

For example: Lets say we have array -2 5 -3. First we sum 5 and -3, so the temporary sum is 2, and our sequence changes to -2 2. Then we sum -2 and 2, so now our temporary sum is 0. As we see, maximum of temporary sums was 2, and we cant get any lower. (summing -2 and 5 would give us 3, which is higher that 2).

My goal on that exam was to find best complexity algorithm, and proof its correctness.

What i tried: First thought was to use greedy algorithm, so just sum those two numbers which give lowest temporary sum right now. Problem is, i cant neither prove it is valid way to solve it, or find any counterexample. So i write here, maybe someone finds it interesting. Thanks for your attention

## Decrypting a password-protected 7z file with Delta filter fails

I have made a 7z archive using Delta filter containing a wav file and I have protected it with a password. I am running a terminal in Kali Linux. My problem is that I cannot get the password cracked using 7z2john.pl and john the ripper. If I omit the Delta compression, using only the default compression of 7z, then the cracking succeeds. My question: is it possible to use 7z2john.pl and john the ripper to crack a password-protected 7z file with Delta compression? If it is possible, how can it be done?

Here are the steps to reproduce the problem:

1. I use the following command to create the archive:

7z a test.7z *.wav -mf=Delta:4 -peasy

I get this output:

7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21 p7zip Version 16.02 (locale=fi_FI.utf8,Utf16=on,HugeFiles=on,64 bits,4 CPUs Intel(R) Core(TM) i5-4460  CPU @ 3.20GHz (306C3),ASM,AES-NI)  Open archive: test.7z -- Path = test.7z Type = 7z Physical Size = 1090 Headers Size = 162 Method = Delta LZMA2:15 7zAES Solid = - Blocks = 1  Scanning the drive: 1 file, 32080 bytes (32 KiB)  Updating archive: test.7z  Items to compress: 1       Files read from disk: 1 Archive size: 1090 bytes (2 KiB) Everything is Ok  
1. I use 7z2john.pl to generate material for John the Ripper to crack the archive:

/usr/share/john/7z2john.pl test.7z > test.hash

1. I create a word list file containing only the password I gave to the archive:

echo easy > wordlist.txt

Then I try to decrypt the file:

sudo john test.hash --wordlist=wordlist.txt

I get the following output:

Using default input encoding: UTF-8 Loaded 1 password hash (7z, 7-Zip [SHA256 256/256 AVX2 8x AES]) Cost 1 (iteration count) is 524288 for all loaded hashes Cost 2 (padding size) is 3 for all loaded hashes Cost 3 (compression type) is 2 for all loaded hashes Will run 4 OpenMP threads Press 'q' or Ctrl-C to abort, almost any other key for status Warning: Only 1 candidate left, minimum 32 needed for performance. 0g 0:00:00:00 DONE (2020-08-15 07:37) 0g/s 5.555p/s 5.555c/s 5.555C/s easy Session completed 
1. I check if the password has been cracked: sudo john --show test.hash

I get the following output:

0 password hashes cracked, 1 left

So it seems that the decrypting did not succeed. However, I can extract the archive using command 7z e test.7z -peasy so the password should be correct. Also, if I create the archive without specifying the Delta filter using command 7z a test.7z *.wav -peasy. That way, by repeating the steps 1-4 I get the password cracked and am shown the result that the correct password has been found: