/sci/ - Science & Math » Thread #11261763

75KiB, 1662x682, turing machine.png

View Same Google iqdb SauceNAO

Anonymous Sun 29 Dec 16:12:01 2019 No.11261763 View Reply Original Report

Quoted By: >>11261777 >>11261781 >>11261826 >>11261828 >>11262195 >>11262237 >>11262245 >>11262274

How do you copy string?
http://morphett.info/turing/turing.html
This site lets you simulate a Turing machine. I want to make a program which copies the input one space further. It's easy to do if you introduce new symbols into the tape besides " ","0", "1", but I can't do it with just these three.
This is not homework, no CS curriculum ever requires their students to do something like this.

As a side question, could you also make a program that adds two numbers without introducing any new symbols? For example, inputting "101101 11" should output "110001", which is their sum

Anonymous

Anonymous Sun 29 Dec 2019 16:28:37 No.11261777 Report

Quoted By: >>11261839

>>11261763
>I want to make a program which copies the input one space further.
If I understand you correctly, I imagine one way to do it is to move to the far right+1 and then repeatedly go two left and copy to one right

abcdefg_. now go two left
abcdef.g_ now copy g to the right
abcdefg.g now go two left
abcde.fgg now copy f to the right
abcdef.fg now go two left
abcd.effg now ... ... etc.

>As a side question, could you also make a program that adds two numbers without introducing any new symbols?
I don't know the binary representation addition algorithm, although the more naive "remove the blank between two sequences of ones" is easy and you can play with it here
https://turingmaschine.klickagent.ch/einband/?&lang=en#2_+_3
and if you want to get more control of the thing I have a C#-dialect implementation of the machine here that you can copy
https://github.com/Nikolaj-K/turing-complete-smart-contract/blob/master/contract.cs#L37
It must be possible, to implement it but the model is more suited to decision procedures. Nevertheless, just googing "Binary addition Turing machine" gives a lot of results, try it. E.g.
http://courses.washington.edu/css502/zander/Notes/14langTuringEx.pdf
(haven't checked that)

Anonymous

Anonymous Sun 29 Dec 2019 16:30:28 No.11261781 Report

Quoted By: >>11261839

>>11261763
every time you add 1, it changes the rightmost 0 to a 1, flipping the 1s in the lower places; the 1 in the nth place from the right does the same while ignoring the n-1 spots before it. This follows from how we add decimals in elementary school arithmetic. To elucidate this process I'll use your example

101101 + 11
=101110 + 10
=(10111 + 1) appended leftwise to 0
=(11000) appended leftwise to 0
= 110000
*you botched your example, but I only realized after applying my method and checking on windows' calculator

I'm just an ideas guy and I forget how programming works though, so the implementation of the loops is up to you.

Anonymous

Anonymous Sun 29 Dec 2019 16:55:26 No.11261826 Report

Quoted By:

>>11261763
op y u no jus write asm on dosbox is like sameo thingo

Anonymous

Anonymous Sun 29 Dec 2019 16:58:37 No.11261828 Report

Quoted By: >>11261839

>>11261763
here you go:
http://morphett.info/turing/turing.html?6df2d0a53f8f201f20eb6d797057196b

Anonymous

Anonymous Sun 29 Dec 2019 17:07:17 No.11261839 Report

Quoted By: >>11261873 >>11262274

>>11261828
Not what I want. You just moved it one to the right.
Example of what i want:
input: "10101011"
output: "10101011 10101011"
---
input: "111011111111"
output:"111011111111 111011111111"
perhaps these will be enough for you to extrapolate the general idea.
>>11261777
you used a lot of letters, the point is that I want to do it only using 1's, 0's and spaces.
>>11261781
i know how this works, I've been able to make an addition algorithm just like what you said using additional x's and y's to represent already added 1's and 0's. My problem is to use ONLY 1's and 0's (and blanks)

Anonymous

Anonymous Sun 29 Dec 2019 17:31:51 No.11261873 Report

Quoted By: >>11261888 >>11261995

>>11261839
>Not what I want
oh
no I don't think you can do that with only 3 states

Anonymous

Anonymous Sun 29 Dec 2019 17:36:31 No.11261888 Report

Quoted By: >>11262143

>>11261873
can you prove that? Also it's not 3 states, you can use however many states you want, but just 3 symbols you can write down on the tape. Although that's probably what you meant.

Anonymous

Anonymous Sun 29 Dec 2019 18:48:39 No.11261995 Report

Quoted By: >>11262052

>>11261873
That's more than you can build a universal Turing machine

Anonymous

Anonymous Sun 29 Dec 2019 19:08:26 No.11262052 Report

Quoted By:

>>11261995
how do you do it then?

Anonymous

Anonymous Sun 29 Dec 2019 19:40:29 No.11262143 Report

Quoted By: >>11262174

>>11261888
>you can use however many states you want
Ooh, my bad.

Here you go then:
http://morphett.info/turing/turing.html?242a9833c5f35e128d8a1099d0c738a0

It's probably a bit convoluted, but it works.

Anonymous

Anonymous Sun 29 Dec 2019 19:58:40 No.11262174 Report

Quoted By: >>11262189

>>11262143
very nice, this is exactly what I wanted. Can you also do addition, and in principle, anything that a modern computer can do?

Anonymous

Anonymous Sun 29 Dec 2019 20:06:40 No.11262189 Report

Quoted By:

>>11262174
yeah
https://en.wikipedia.org/wiki/Universal_Turing_machine
>When Alan Turing came up with the idea of a universal machine he had in mind the simplest computing model powerful enough to calculate all possible functions that can be calculated.
>Claude Shannon first explicitly posed the question of finding the smallest possible universal Turing machine in 1956.
>He showed that two symbols were sufficient so long as enough states were used (or vice versa), and that it was always possible to exchange states for symbols.

Anonymous

Anonymous Sun 29 Dec 2019 20:11:40 No.11262195 Report

Quoted By:

>>11261763
>>>/g/

Anonymous

Anonymous Sun 29 Dec 2019 20:33:48 No.11262237 Report

Quoted By:

>>11261763
>. I want to make a program which copies the input one space further. It's easy to do if you introduce new symbols into the tape besides " ","0", "1", but I can't do it with just these three.

Instead of introducing new symbols just store it in the state.

>Starting condition
An infinite tape with a string consisting of '1' and '0' and terminated with ' ' with read head at the beginning.

>Ending condition
An infinite tape with the string consisting of '1' and '0' and terminated with ' ' with ' ' appended in the beginning and read head at the end.

>States
starting, stored_0, stored_1, finishing, finished

>Transitions
(state=starting, tape=0) -> (write=' ', shift_head=right, state=stored_0)
(state=starting, tape=1) -> (write=' ', shift_head=right, state=stored_1)
(state=stored_0, tape=0) -> (write='0', shift_head=right, state=stored_0)
(state=stored_1, tape=0) -> (write='1', shift_head=right, state=stored_0)
(state=stored_1, tape=1) -> (write='1', shift_head=right, state=stored_1)
(state=stored_0, tape=1) -> (write='0', shift_head=right, state=stored_1)
(state=stored_0, tape=' ') -> (write='0', shift_head=right, state=finishing)
(state=stored_1, tape=' ') -> (write='1', shift_head=right, state=finishing)
(state=finishing, tape=X) -> (write=' ', state=finished)

>This is not homework, no CS curriculum ever requires their students to do something like this.

Because it's so easy

Anonymous

Anonymous Sun 29 Dec 2019 20:36:38 No.11262245 Report

Quoted By: >>11262253

>>11261763
>101101 11" should output "110001
45+3=48 not 49

Anonymous

Anonymous Sun 29 Dec 2019 20:40:25 No.11262253 Report

Quoted By:

>>11262245
Have sex

Anonymous

Anonymous Sun 29 Dec 2019 20:52:47 No.11262274 Report

Quoted By:

>>11261763
>As a side question, could you also make a program that adds two numbers without introducing any new symbols?

>>11261839
>i know how this works, I've been able to make an addition algorithm just like what you said using additional x's and y's to represent already added 1's and 0's. My problem is to use ONLY 1's and 0's (and blanks)

shift them both by 1
shift the second by another 1
find the first digits of both strings and save into state
swap first digits with space thus creating 5 strings
add saving sum and carry into state
write sum at the end
find the first digit of the 2nd and 4th strings
swap with the preceding space
add + carry state and save into state
goto 4 lines up
when 2nd and 4th are finished, write carry to the end

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches