Differences

This shows you the differences between two versions of the page.

--- tanszek:oktatas:techcomm:system:system [2024/10/07 06:11] – knehez
+++ tanszek:oktatas:techcomm:system:system [2026/09/28 16:31] (current) – knehez
@@ Line 5: / Line 5: @@
 {{:tanszek:oktatas:techcomm:system:pasted:20241007-060022.png}}
-In the example system, there are elements belonging to classes A, B, and C, and there are connections of types 'a' and 'b'. The state equations, which serve as the mathematical model of the system, may be differential or difference equations. The state equations describe the state changes of the system.
+In the example system, there are elements belonging to classes **A**, **B**, and **C**, and there are connections of types 'a' and 'b'. The __state equations__, which serve as the mathematical model of the system, may be differential or difference equations. The __state equations__ describe the state changes of the system.
-The internal state of the system is described by physical state indicators. In the system model, the state indicators correspond to state variables. Interactions between the elements of the system involve the transfer of energy and information. From an information technology perspective, state variables are referred to as signals. Any state indicator that is observable and capable of carrying information can be considered a //signal//.
+Physical state indicators describe the system's internal state. In the system model, the state indicators correspond to state variables. Interactions between the elements of the system involve the transfer of energy and information. From an information technology perspective, state variables are called **signals**. Any observable state indicator that can carry information can be considered a //signal//.
 **Example**
@@ Line 13: / Line 13: @@
 {{:tanszek:oktatas:techcomm:system:pasted:20241007-060609.png}}
+===== Turing Machine: Add One to a Binary Number =====
+==== What Is a Turing Machine? ====
+A **Turing machine** is a simple mathematical model of a computer. It has a tape divided into cells, a read/write head, and a finite set of states. The tape provides unlimited memory, and each cell contains one symbol. At each step, the machine reads the symbol under the head. Based on this symbol and its current state, it writes a symbol, moves the head, and selects the next state. These actions follow fixed rules called **transitions**. Although its structure is simple, a Turing machine can perform any computation describable by an algorithm, given enough time and tape.
+==== Task ====
+A binary number is written on the tape. The reading head starts at the first digit.
+<mermaid>
+block-beta
+    columns 5
+    head["Head: q0"] space:4
+    a["1"] b["0"] c["1"] d["1"] e["□"]
+    head --> a
+    style a fill:#fff0b3,stroke:#cc8800,stroke-width:3px
+</mermaid>
+Create a Turing machine that adds **1** to the number and then stops.
+Examples:
+  * 1011 → 1100
+  * 1010 → 1011
+  * 111 → 1000
+  * 0 → 1
+The input contains at least one digit. All other cells are blank. The tape can extend in both directions.
+==== Symbols ====
+  * **0, 1:** binary digits
+  * **□:** a blank cell
+  * **R:** move one cell to the right
+  * **L:** move one cell to the left
+  * **S:** stay in the same cell
+Each arrow in the diagram has this format:
+  read symbol / write symbol, movement
+For example, **1 / 0, L** means: read 1, write 0, and move left.
+==== Algorithm ====
+  - Move right until you find a blank cell after the number.
+  - Move left to the last digit.
+  - If the digit is **1**, write **0** and move left. Continue adding the carry.
+  - If the digit is **0**, write **1** and stop.
+  - If you reach a blank cell before the number, write **1** and stop.
+==== States ====
+^ State ^ Meaning ^
+| q0 | Move right to find the end of the number. This is the start state. |
+| q1 | Add 1 to the current digit. |
+| qH | Stop. |
+**The carry is stored in state q1.** No extra variable is needed.
+If the machine reads 1 in q1, it writes 0 and moves left. It stays in q1 because it still has a carry.
+If it reads 0 in q1, it writes 1 and stops. There is no carry left.
+==== State Diagram ====
+<mermaid>
+stateDiagram-v2
+    [*] --> q0
+    q0 --> q0: 0 / 0, R
+    q0 --> q0: 1 / 1, R
+    q0 --> q1: □ / □, L
+    q1 --> q1: 1 / 0, L
+    q1 --> qH: 0 / 1, S
+    q1 --> qH: □ / 1, S
+    qH --> [*]
+</mermaid>
+==== Transition Table ====
+^ Current state ^ Read ^ Write ^ Move ^ Next state ^
+| q0 | 0 | 0 | R | q0 |
+| q0 | 1 | 1 | R | q0 |
+| q0 | □ | □ | L | q1 |
+| q1 | 1 | 0 | L | q1 |
+| q1 | 0 | 1 | S | qH |
+| q1 | □ | 1 | S | qH |
+==== Example: 1011 + 1 ====
+Square brackets show the position of the reading head.
+^ Step ^ State ^ Tape ^ Next action ^
+| 0 | q0 | [1]011□ | Move right. |
+| 1 | q0 | 1[0]11□ | Move right. |
+| 2 | q0 | 10[1]1□ | Move right. |
+| 3 | q0 | 101[1]□ | Move right. |
+| 4 | q0 | 1011[□] | Move left and enter q1. |
+| 5 | q1 | 101[1]□ | Write 0, move left, keep the carry. |
+| 6 | q1 | 10[1]0□ | Write 0, move left, keep the carry. |
+| 7 | q1 | 1[0]00□ | Write 1 and enter qH. |
+| 8 | qH | 1[1]00□ | The machine has stopped. |
+The result is **1100**.
+The leftmost digit does not change because the carry ends before the head reaches it.
+==== What Happens with 111? ====
+After finding the end, the machine changes each 1 to 0 and moves left.
+It then reaches the blank cell before the number. It writes 1 there and stops.
+The result is **1000**.
+==== Practice ====
+Trace the machine for these inputs. Write down the state and the head position after each step.
+  - 1010
+  - 111
+  - 0
+Why does the machine stay in q1 after changing a 1 to a 0?
 ===== Signal =====
@@ Line 20: / Line 146: @@
 There are signals with constant values over time and those with changing values over time. Information is often conveyed by the change in the signal over time. The four main types of signals are:
-**1. Analog signals**
+**1. Analog signal**
 The signal is continuous in both time and value.
@@ Line 26: / Line 152: @@
 The signal is discrete in value.
-**3. Sampled signals**
+**3. Sampled signal**
 The signal is discrete in time.
@@ Line 34: / Line 160: @@
 The mathematical model of signals: a time-varying function. The model of a signal can be deterministic or stochastic. A stochastic signal is a composition of the useful signal and noise. A stochastic signal changes randomly. Stochastic signals can only be modelled using statistical methods.
-{{:tanszek:oktatas:techcomm:system:pasted:20241007-061106.png}}
+{{:tanszek:oktatas:techcomm:system:pasted:20260928-162912.png}}