MOV is Turing complete

[idle]

This was a good morning read.
https://leetarxiv.substack.com/p/mov-is ... ementation

This effectively performs an If with mov, compile with x86 Assembler back end

Code: Select all

DataSection 
  !memory: rd 256 
  !value1: dd 10     ;change to 20 
  !value2: dd 20 
  !result: dd 0 
  out: 
EndDataSection

!mov eax, ptr value1
!mov dword [memory + eax], 0
; Step 2: Store 1 at memory[value2]
!mov eax, [value2]              ; Load value2 into eax
!mov byte [memory + eax], 1     ; Store 1 at memory[value2]

; Step 3: Read the value at memory[value1] into result
!mov eax, [value1]               ; Load value1 into eax
!mov bl, [memory + eax]     ; Move the value at memory[value1] into bl
!mov byte [result], bl           ; Move the value of bl into result

Debug PeekL(?out-4)

[Denis]

Interesting.

Thanks idle.

[BarryG]

This is waaaaay above my understanding.

[idle]

This is waaaaay above my understanding.

Mine too before my morning coffee.
I often read cs articles and papers with my morning coffee better than trumpagedon and muskrat.

[miso]

I lack both the needed assembly and math skills to understand this, though I was always fascinated by cellular automatons. Conway's Game of life is
also turing complete, heres a video where Game of life runs Game of life in itself infinitely.

https://youtu.be/4lO0iZDzzXk

[PBJim]

I think this is a daft exercise by someone lacking better things to do, but nevertheless interesting all the same. A CPU must have a reasonable instruction set in order to make programming a practical and viable proposition at all.

He contradicts his below statement, when he goes on to provide the code example, which requires more than just MOV

This proves we can create a turing-complete language using only mov.

Code: Select all

    ; Step 4: Convert the value in result to ASCII
    add byte [result], '0'  ; Convert 0 to '0' or 1 to '1'
    mov al, [result]        ; Load the value of result into al
    mov [output], al        ; Store the ASCII value in the output string

    ; Step 5: Print the value in result (just to see outout)
    mov eax, 1          ; syscall: write
    mov edi, 1          ; file descriptor: stdout
    lea rsi, [output]   ; address of output string
    mov edx, 1          ; number of bytes to write
    syscall

    ; Exit the program
    mov eax, 60         ; syscall: exit
    xor edi, edi        ; status: 0
    syscall

[idle]

Yes the paper is an academic taking a poke for sure it's a clever trick

[idle]

I lack both the needed assembly and math skills to understand this, though I was always fascinated by cellular automatons. Conway's Game of life is
also turing complete, heres a video where Game of life runs Game of life in itself infinitely.

https://youtu.be/4lO0iZDzzXk

I'm keeping that, thanks that's very cool