Page 1 of 1

MOV is Turing complete

Posted: Sun Jan 26, 2025 8:05 pm
by 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)


Re: MOV is Turing complete

Posted: Mon Jan 27, 2025 9:58 am
by Denis
Interesting.

Thanks idle.

Re: MOV is Turing complete

Posted: Mon Jan 27, 2025 12:43 pm
by BarryG
This is waaaaay above my understanding. :lol:

Re: MOV is Turing complete

Posted: Mon Jan 27, 2025 7:44 pm
by idle
BarryG wrote: Mon Jan 27, 2025 12:43 pm This is waaaaay above my understanding. :lol:
Mine too before my morning coffee.
I often read cs articles and papers with my morning coffee better than trumpagedon and muskrat.

Re: MOV is Turing complete

Posted: Tue Jan 28, 2025 10:37 am
by 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

Re: MOV is Turing complete

Posted: Tue Jan 28, 2025 2:02 pm
by 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 :D
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

Re: MOV is Turing complete

Posted: Tue Jan 28, 2025 7:30 pm
by idle
Yes the paper is an academic taking a poke for sure it's a clever trick

Re: MOV is Turing complete

Posted: Tue Jan 28, 2025 7:44 pm
by idle
miso wrote: Tue Jan 28, 2025 10:37 am 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